oj.uz

Submission #449839

# Submission time Handle Problem Language Result Execution time Memory
449839 2021-08-02T08:30:52 Z ritul_kr_singh Traffic (CEOI11_tra) C++17
100 / 100
 736 ms 50160 KB 
#include <bits/stdc++.h>
using namespace std;
#define X p[i][1]
#define I p[i][2]
 
const int Z = 3e5+1;
 
int n, m, A, B, dfsNum[Z], id[Z], L[Z], R[Z], pre[Z], dfsTimer, st[Z], stP;
vector<int> g[Z], h[Z];
array<int, 3> p[Z];
 
int dfs(int u){
	int low = dfsNum[u] = ++dfsTimer;
	st[stP++] = u;
	for(int &v : g[u])
		if(!id[v]) low = min(low, dfsNum[v] ? : dfs(v));
	if(low == dfsNum[u]){
		for(int c=0; c!=u; ){
			id[c = st[--stP]] = u;
			for(int &v : g[c]){
				L[u] = min(L[u], L[(id[v] ? : u) == u ? v : id[v]]);
				R[u] = max(R[u], R[(id[v] ? : u) == u ? v : id[v]]);
			}
		}
	}
	return low;
}
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> A >> B;
 
	fill(L, L+n+1, n+1);
 
	for(int i=0; i<n; ++i){
		cin >> X >> p[i][0];
		I = i+1;
	}
 
	for(int i=0; i<m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back(v);
		if(w > 1) g[v].push_back(u);
	}
 
	sort(p, p+n);

	for(int i=0; i<n; ++i)
		if(X == A) L[I] = R[I] = i+1;
 
	for(int i=0; i<n; ++i)
		if(!X && !dfsNum[I]) dfs(I);
 
	for(int i=0; i<n; ++i)
		pre[i+1] = pre[i] + (dfsNum[I] && X == A);
 
	for(int i=n; --i>=0; ){
		int j = id[I];
		if(!X)
			cout << (R[j] ? pre[R[j]] - pre[L[j]-1] : 0) << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14540 KB Output is correct
3 Correct 8 ms 14412 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 10 ms 14420 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 8 ms 14424 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14424 KB Output is correct
2 Correct 9 ms 14428 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14540 KB Output is correct
2 Correct 13 ms 14820 KB Output is correct
3 Correct 12 ms 14668 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16300 KB Output is correct
2 Correct 53 ms 18660 KB Output is correct
3 Correct 40 ms 16252 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 17544 KB Output is correct
2 Correct 66 ms 20664 KB Output is correct
3 Correct 59 ms 18308 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 21128 KB Output is correct
2 Correct 121 ms 24832 KB Output is correct
3 Correct 161 ms 24540 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 23176 KB Output is correct
2 Correct 137 ms 25256 KB Output is correct
3 Correct 186 ms 25176 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 28940 KB Output is correct
2 Correct 218 ms 32808 KB Output is correct
3 Correct 361 ms 34952 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 37896 KB Output is correct
2 Correct 409 ms 44092 KB Output is correct
3 Correct 380 ms 36364 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 49684 KB Output is correct
2 Correct 391 ms 46320 KB Output is correct
3 Correct 732 ms 48268 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 33220 KB Output is correct
2 Correct 473 ms 48460 KB Output is correct
3 Correct 567 ms 45628 KB Output is correct
4 Correct 736 ms 50160 KB Output is correct