# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1117299 | manizare | Traffic (CEOI11_tra) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5 + 10, inf = 1e9+10 , mod = 998244353 ;
vector <pii>f[maxn];
vector <pii> si ;
int x[maxn] ,y[maxn] , ok[maxn] , n , a, b, m , l[maxn] ,r[maxn] , c[maxn];
bool mark[maxn] , ch[maxn] ;
vector <int> G[maxn] , tp , Gr[maxn] ;
vector <pii> cp ;
void dfs2(int r){
vector <int> st ;
st.pb(r) ;
while(sz(st)){
int v = st.back() ; st.pop_back() ;
ch[v] = 1;
for(int u : G[v]){
if(mark[u] ==0)continue ;
if(ch[u] == 0)st.pb(u) ;
l[c[v]] = min(l[c[v]] , l[c[u]]) ;
r[c[v]] = max(r[c[v]] , r[c[u]]) ;
}
}
}
void dfs(int v){
mark[v] = 1;
if(x[v] == a)ok[v] =1 ;
for(int u : G[v]){
if(mark[u] == 1)continue ;
dfs(u) ;
}
tp.pb(v) ;
}
int cnt= 1;
void dfs4(int v){
c[v] = cnt ;ch[v] = 1;
for(int u : Gr[v]){
if(ch[u] == 1 || mark[u] == 0)continue ;
dfs4(u) ;
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n>> m >> a >> b ;
vector <int> sr ;
rep(i , 1, n){
cin >> x[i] >> y[i] ;
if(x[i] == 0){
sr.pb(i) ;
}
if(x[i]==0||x[i]==a)
cp.pb({y[i] , i});
l[i] = inf ;
r[i] = -inf ;
}
sort(all(cp));
rep(i ,1 ,m){
int v, u , k;
cin >> v >> u >> k;
Gr[u].pb(v);
G[v].pb(u);
if(k==2){
G[u].pb(v) ;
Gr[v].pb(u);
}
}
for(int x : sr){
if(mark[x] == 0)dfs(x) ;
}
rep(i ,1 ,n)ch[i] =0 ;
per(i , sz(tp)-1 , 0){
int v =tp[i] ;
if(ch[v] == 0){
dfs4(v) ;
cnt++ ;
}
}
int ted= 0;
rep(i , 0, sz(cp)-1){
int v= cp[i].S ;
if(ok[v] == 0)continue ;
l[c[v]] = min(l[c[v]] , ted);
r[c[v]] = max(r[c[v]] , ted);
ted ++ ;
}
rep(i ,1 ,n)ch[i] =0 ;
for(int x : sr){
if(mark[x] == 1 && ch[x] == 0)dfs2(x) ;
}
per(i , n-1 , 0){
int w = cp[i].S ;
if(x[w] != 0)continue ;
if(l[c[w]] == inf || mark[w] == 0){
cout << 0 << "\n";
}else{
cout << r[c[w]]-l[c[w]]+1<< "\n" ;
}
}
return 0 ;
}
/*
*/