Submission #1226737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226737		erering	Traffic (CEOI11_tra)	C++20	100 / 100	732 ms	62304 KiB

tra

#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define endl '\n'
using namespace std;
using ll=long long;
const int MAXN=3e5+5,inf=2e18;
vector<int> adj[MAXN],rev[MAXN];
pair<int,int> p[MAXN];
bool vis[MAXN];
int mn[MAXN],mx[MAXN];
void dfs(int node){
    vis[node]=1;
    for(auto i:adj[node]){
        if(!vis[i])dfs(i);
    }
}
void dfs2(int node,int cnt){
    mn[node]=cnt;
    for(auto i:rev[node]){
        if(mn[i]==0)dfs2(i,cnt);
    }
}
void dfs3(int node,int cnt){
    mx[node]=cnt;
    for(auto i:rev[node]){
        if(mx[i]==0)dfs3(i,cnt);
    }
}
signed main(){
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     int n,m,a,b; cin>>n>>m>>a>>b;
     vector<pair<int,int>> bro;
     for(int i=1;i<=n;i++){
         cin>>p[i].first>>p[i].second;
         if(p[i].first==0)bro.pb({p[i].second,i});
     }
     for(int i=0;i<m;i++){
         int c,d,k; cin>>c>>d>>k;
         adj[c].pb(d);
         rev[d].pb(c);
         if(k==2){
             adj[d].pb(c);
             rev[c].pb(d);
         }
     }
     for(int i=1;i<=n;i++){
         if(p[i].first==0 && !vis[i])dfs(i);
     }
     vector<pair<int,int>> vec;
     for(int i=1;i<=n;i++){
         if(p[i].first==a && vis[i])vec.pb({p[i].second,i});
     }
     cout<<endl;
     sort(vec.begin(),vec.end());
     for(int i=0;i<vec.size();i++){
         if(mn[vec[i].second]==0)dfs2(vec[i].second,i+1);
     }
     for(int i=vec.size()-1;i>=0;i--){
         if(mx[vec[i].second]==0)dfs3(vec[i].second,i+1);
     }
     sort(bro.begin(),bro.end());
     for(int i=bro.size()-1;i>=0;i--){
         int id=bro[i].second;
         cout<<(mx[id]==0?0:mx[id]-mn[id]+1)<<endl;
     }
}

• 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