Submission 831 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
831	15/05/2013 22:50:27	leandro	F - Tesoros escondidos	Accepted	31	2.2 KiB	GNU G++ 5.1.0

Code

/*
    username: leandro
    program: Tesoros
    lang: C++
*/

#include <cstdio>

const int
      MaxV = 10000 + 10,
	  MaxE = 100000 + 10;

struct edg {
    int dest;
	int next;
	edg() { }
	edg(int a, int b) :
	    dest(a), next(b) { }
};
	  
int V, E;
int i, j;
int cost[MaxV];
int first[MaxV];
edg edges[MaxE];

bool bio[MaxV];

int gtime;
int disc[MaxV];
int back[MaxV];
int S[MaxV], size;

int sccnum;
int scc[MaxV];
int value[MaxV];
bool erase[MaxV];
int first2[MaxV];
edg edges2[MaxE];

inline int min(const int& a, const int& b) {
    return (a < b) ? a : b;
}

inline int max(const int& a, const int& b) {
    return (a > b) ? a : b;
}

void dfs(int v) {
    
	bio[v] = true;
	
	gtime++;
	back[v] = gtime;
	disc[v] = gtime;
	
	S[size++] = v;
	
	for (int k = first[v]; k != -1; k = edges[k].next)
	    if (bio[edges[k].dest] == false) {
		    dfs(edges[k].dest);
			back[v] = min(back[v], back[edges[k].dest]);
		} else if (!erase[edges[k].dest])
		    back[v] = min(back[v], disc[edges[k].dest]);
	
	if (disc[v] == back[v]) {
	    while (size) {
		    int node = S[--size];
			scc[node] = sccnum;
			erase[node] = true;
			value[sccnum] += cost[node];
			if (node == v)
			    break;
		}
		sccnum++;
	}
	
}

int memo(int v) {
    if (bio[v])
	    return value[v];
    bio[v] = true;
	int ret = -(1 << 25);
	for (int k = first2[v]; k != -1; k = edges2[k].next)
	    ret = max(ret, memo(edges2[k].dest));
	value[v] = value[v] + ret;
	return value[v];
}

int main() {
    	
	scanf("%d%d", &V, &E);
	
	/* ini */
	for (i = 0; i < V; i++) {
	    bio[i] = false;
	    first[i] = -1;
	}
	
	/* read */
	for (i = 0; i < V; i++)
	    scanf("%d", &cost[i]);
	
	for (i = 0; i < E; i++) {
	    int a, b;
		scanf("%d%d", &a, &b);
		edges[i] = edg(b, first[a]);
		first[a] = i;
	}
	
	/* get scc */
	for (i = 0; i < V; i++)
	    if (bio[i] == false) dfs(i);
	
	/* scc's graph (inverse) */
	for (i = 0; i < sccnum; i++) {
	    bio[i] = false;
	    first2[i] = -1;
	}
	
	E = 0;
	for (i = 0; i < V; i++)
	    for (j = first[i]; j != -1; j = edges[j].next)
		    if (scc[i] != scc[edges[j].dest]) { //avoid loops on the same scc
		        edges2[E] = edg(scc[i], first2[scc[edges[j].dest]]);
			    first2[scc[edges[j].dest]] = E++;
		    }
	
	bio[scc[0]] = true;
	printf("%d\n", max(memo(scc[V-1]), 0));
	
	fflush(stdout);
	return 0;
	
}

Judgement Details

Test 01: 0.010 0.000 1296K ok
Test 02: 0.020 0.031 2228K ok
Test 03: 0.009 0.000 1296K ok
Test 04: 0.009 0.000 1300K ok
Test 05: 0.008 0.000 1300K ok
Test 06: 0.009 0.000 1296K ok
Test 07: 0.011 0.000 1368K ok
Test 08: 0.012 0.000 1436K ok
Test 09: 0.016 0.000 1608K ok
Test 10: 0.024 0.016 1848K ok
Accepted

Matcom Online Grader