oj.uz

Submission #651050

# Submission time Handle Problem Language Result Execution time Memory
651050 2022-10-16T16:18:40 Z lovrot Traffic (CEOI11_tra) C++17
100 / 100
 989 ms 64728 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define pii pair<int, int>
#define pb push_back 

using namespace std;

const int N = 3 * 1e5 + 10;
const int INF = 1e9 + 10;

int ans[N], comp[N];
int in[N], diff[N], t;

bool vis[N], cvis[N], isol[N]; 

vector<pii> tout, start;
vector<int> g[2][N], topo[N], fin;

void visAll(int u){
	vis[u] = true;
	for(int v : g[1][u]){
		if(!vis[v]) visAll(v); 
	}
}

void timer(int u){
	vis[u] = true;
	for(int v : g[0][u]){
		if(vis[v]) continue;
		timer(v);
	}	
	tout.pb({t, u});
	t++;
}

void scc(int u, int p){ 
	vis[u] = true;
	comp[u] = p;
//	printf("%d\n", u);
	for(int v : g[1][u]){
		if(vis[v]){
			if(comp[v] != p) topo[comp[v]].pb(p);
			continue;
		}
		scc(v, p);
	}
} 

int rec(int u){
	if(vis[u]) return 0;
	vis[u] = true;
	int ret = in[u];
	for(int v : topo[u]){
		ret += rec(v);
	} 
//	printf("%d, ret = %d\n", u, ret);
	return ret;
}

int main(){
	int n, m, A, B;
	scanf("%d%d%d%d", &n, &m, &A, &B);
	
	for(int i = 1; i <= n; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		if(x == 0) start.pb({y, i});
		if(x == A) fin.pb(i);
	}
	
	sort(start.begin(), start.end(), [](pii a, pii b) -> bool {return a.X > b.X;});
	
//	for(pii p : start) printf("x = %d y = %d\n", p.X, p.Y);
	
	for(int i = 0; i < m; i++){
		int u, v, t;
		scanf("%d%d%d", &u, &v, &t);
		if(t == 1){
			g[0][u].pb(v);
			g[1][v].pb(u);
		} else {
			g[0][u].pb(v);
			g[1][v].pb(u);
			g[0][v].pb(u);
			g[1][u].pb(v);
		}
	}
	
	for(int u : fin){
		if(vis[u]) continue;
		visAll(u);
	}
	
	for(pii p : start){
		if(!vis[p.Y]) isol[p.Y] = true;
	}
	
	memset(vis, 0, sizeof(vis));
	
	for(int i = 1; i <= n; i++){
		if(vis[i]) continue;
		timer(i);
	}
		
	sort(tout.begin(), tout.end(), [](pii a, pii b) -> bool {return a.X > b.X;});
	
	memset(vis, 0, sizeof(vis));	
		
	int cnt = 0; 
	for(pii p : tout){
		if(vis[p.Y]) continue;
		cnt++;
//		printf("new head: %d\n", cnt);
		scc(p.Y, cnt);
	}
		
	for(int i = 1; i <= cnt; i++) topo[i].erase(unique(topo[i].begin(), topo[i].end()), topo[i].end());
	
	for(int u : fin) in[comp[u]]++;
	
	memset(vis, 0, sizeof(vis));	
			
	for(int i = start.size() - 1; i >= 0; i--){
		int u = start[i].Y;
		if(isol[u]) continue;
		diff[u] = rec(comp[u]);	
//		printf("u = %d diff = %d\n", comp[u], diff[u]);
	}	
	
	memset(vis, 0, sizeof(vis));
	
	int res = 0;
	for(pii p : start){
		int u = p.Y;
		if(isol[u]){
			printf("0\n");
			continue;
		}
		res += rec(comp[u]);
		printf("%d\n", res);
		res -= diff[u];
	}
	return 0;
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d%d%d%d", &n, &m, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tra.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
tra.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d%d", &u, &v, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21676 KB Output is correct
2 Correct 14 ms 21716 KB Output is correct
3 Correct 12 ms 21752 KB Output is correct
4 Correct 11 ms 21716 KB Output is correct
5 Correct 15 ms 21756 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21744 KB Output is correct
2 Correct 13 ms 21716 KB Output is correct
3 Correct 13 ms 21716 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21716 KB Output is correct
2 Correct 12 ms 21812 KB Output is correct
3 Correct 12 ms 21820 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21844 KB Output is correct
2 Correct 16 ms 22344 KB Output is correct
3 Correct 16 ms 22112 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23168 KB Output is correct
2 Correct 63 ms 28452 KB Output is correct
3 Correct 39 ms 25124 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 25176 KB Output is correct
2 Correct 88 ms 30164 KB Output is correct
3 Correct 69 ms 28312 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 28768 KB Output is correct
2 Correct 136 ms 37728 KB Output is correct
3 Correct 209 ms 35748 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 29760 KB Output is correct
2 Correct 148 ms 36456 KB Output is correct
3 Correct 269 ms 35056 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 35000 KB Output is correct
2 Correct 297 ms 47496 KB Output is correct
3 Correct 534 ms 44724 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 43432 KB Output is correct
2 Correct 487 ms 60592 KB Output is correct
3 Correct 532 ms 47764 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 50472 KB Output is correct
2 Correct 538 ms 62280 KB Output is correct
3 Correct 914 ms 52708 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 36628 KB Output is correct
2 Correct 588 ms 64728 KB Output is correct
3 Correct 758 ms 54540 KB Output is correct
4 Correct 982 ms 60352 KB Output is correct