Submission #449839

#	Time	Username	Problem	Language	Result	Execution time	Memory
449839		ritul_kr_singh	Traffic (CEOI11_tra)	C++17	100 / 100	736 ms	50160 KiB

tra

#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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9