| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1226927 | Khalid_Alabdullatif | Traffic (CEOI11_tra) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
#define mn first
#define mx second
using namespace std;
const int N=3e5 + 1,mod=1e9 + 7;
const int hx[4] = {0,0,1,-1},hy[4] = {1,-1,0,0},dx[4] = {1,1,-1,-1},dy[4] = {1,-1,1,-1};
int n,m,A,B;
pair<int,int>a[N];
map<pair<int,int>,vector<pair<int,int>>>v;
map<pair<int,int>,bool>vis;
map<pair<int,int>,pair<int,int>>ans;
vector<int>l,r;
map<int,int>idxr; // give y get idx in r
void dfs(pair<int,int>idx){
vis[idx] = 1;
for(auto i:v[idx]){
if(!vis[i])
dfs(i);
}
}
void adfs(pair<int,int>idx){
vis[idx] = 1;
sort(v[idx].begin(),v[idx].end());
reverse(v[idx].begin(),v[idx].end());
for(auto i:v[idx]){
if(!vis[i])
adfs(i);
ans[idx].mn = min(ans[idx].mn,ans[i].mn);
ans[idx].mx = max(ans[idx].mx,ans[i].mx);
}
//cout<<idx.x<<" "<<idx.y<<" ans: "<<ans[idx].mn<<" "<<ans[idx].mx<<endl;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m>>A>>B;
for(int i = 1;i <= n;i++){
cin>>a[i].x>>a[i].y;
if(a[i].x == 0)
l.push_back(a[i].y);
}
while(m--){
int c,d,k;
cin>>c>>d>>k;
if(k == 1){
v[a[c]].push_back(a[d]);
}
else{
v[a[c]].push_back(a[d]);
v[a[d]].push_back(a[c]);
}
}
//cout<<v[{0,1}][0].x<<v[{0,1}][0].y;
for(int i = 1;i <= n;i++){
if(a[i].x == 0)
dfs(a[i]);
}
for(int i = 1;i <= n;i++){
ans[a[i]] = {2e9,0};
if(vis[a[i]] && a[i].x == A){
r.push_back(a[i].y);
}
}
sort(r.begin(),r.end());
//reverse(r.begin(),r.end());
sort(l.begin(),l.end());
reverse(l.begin(),l.end());
vis.clear();
for(int i = 0;i < r.size();i++){
ans[{A,r[i]}].mn = i,ans[{A,r[i]}].mx = i;
//vis[{A,r[i]}] = 1;
}
for(int i = 0; i < l.size();i++){
adfs({0,l[i]});
cout<<max(0,ans[{0,l[i]}].mx - ans[{0,l[i]}].mn + 1)<<"\n";
}
}