제출 #1226917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226917		Almonther	Traffic (CEOI11_tra)	C++20	100 / 100	545 ms	69544 KiB

tra

#include<bits/stdc++.h>

#define ll long long
#define co cout<<

using namespace std;
// stuff
const int maxn=3e5+5;
ll n,m,r,r1;
pair<ll,ll>arr[maxn];
vector<ll>v[maxn],curr,v1[maxn];
ll graph[maxn],vis[maxn];
ll north[maxn],south[maxn],can=0,last=0;
void makegraph(ll x){
    if(graph[x]) return;
    graph[x]=1;
    for(auto i:v1[x]) makegraph(i);
}
ll dfs(ll x,ll type){
    if(vis[x]){
        if(vis[x]==2) can=1;
        if(type==0) return -1e18;
        return 1e18;
    }
    vis[x]=1;
    ll smth=-1e18;
    if(type) smth=1e18;
    if(arr[x].first==r) smth=arr[x].second;
    for(auto i:v[x]){
        if(graph[i]==0) continue;
        if(type==0) smth=max(smth,dfs(i,type));
        else smth=min(smth,dfs(i,type));
    }
    return smth;
}
void makevis(ll x){
    if(vis[x]==2) return;
    vis[x]=2;
    for(auto i:v[x]) makevis(i);
}
void solve(){
    cin>>n>>m>>r>>r1;
    vector<pair<ll,ll>>s;
    for(int i=1;i<=n;i++) cin>>arr[i].first>>arr[i].second;
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        v[a].push_back(b);
        v1[b].push_back(a);
        if(c==2){
            v[b].push_back(a);
            v1[a].push_back(b);
        }
    }
    for(int i=1;i<=n;i++) if(arr[i].first==r) makegraph(i);
    for(int i=1;i<=n;i++){
        if(arr[i].first==0&&graph[i]==1) s.push_back({-arr[i].second,i});
    }
    sort(s.begin(),s.end());
    reverse(s.begin(),s.end());
    for(int i=0;i<s.size();i++){
        north[s[i].second]=dfs(s[i].second,0);
        makevis(s[i].second);
        if(can) north[s[i].second]=max(north[last],north[s[i].second]);
        can=0;
        if(north[s[i].second]!=-1e18) last=s[i].second;
    }
    memset(vis,0,sizeof(vis));
    reverse(s.begin(),s.end());
    for(int i=0;i<s.size();i++){
        south[s[i].second]=dfs(s[i].second,1);
        makevis(s[i].second);
        if(can) south[s[i].second]=min(south[last],south[s[i].second]);
        can=0;
        if(south[s[i].second]!=1e18) last=s[i].second;
    }
    s.clear();
    for(int i=1;i<=n;i++){
        if(arr[i].first==0) s.push_back({-arr[i].second,i});
        if(arr[i].first==r&&graph[i]==1&&vis[i]==2) curr.push_back(arr[i].second);
    }
    sort(curr.begin(),curr.end());
    sort(s.begin(),s.end());
    for(auto i:s){
        if(graph[i.second]==0){
            co "0\n";
            continue;
        }
        ll idx=lower_bound(curr.begin(),curr.end(),north[i.second])-curr.begin();
        ll idx1=lower_bound(curr.begin(),curr.end(),south[i.second])-curr.begin();
        co max(0ll,idx-idx1+1)<<'\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--) solve();
}

• 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