oj.uz

Submission #651041

# Submission time Handle Problem Language Result Execution time Memory
651041 2022-10-16T14:48:47 Z lovrot Traffic (CEOI11_tra) C++17
8 / 100
 983 ms 62148 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);
	} 
	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--){
		if(isol[start[i].Y]) continue;
		int u = comp[start[i].Y];
		diff[u] = rec(u);	
	}	
	
	memset(vis, 0, sizeof(vis));
	
	int res = 0;
	for(pii p : start){
		if(isol[p.Y]){
			printf("0\n");
			continue;
		}
		int u = comp[p.Y];
		res += rec(u);
		ans[u] = res;
		res -= diff[u];
		printf("%d\n", ans[u]);
	}
	return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21716 KB Output is correct
2 Correct 13 ms 21716 KB Output is correct
3 Correct 12 ms 21716 KB Output is correct
4 Correct 12 ms 21704 KB Output is correct
5 Correct 11 ms 21700 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21716 KB Output is correct
2 Incorrect 11 ms 21716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 21716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 21924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 26404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 31424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 31908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 265 ms 37824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 445 ms 50004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 983 ms 62148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 41748 KB Output isn't correct
2 Halted 0 ms 0 KB -