Submission #494969

#	Time	Username	Problem	Language	Result	Execution time	Memory
494969		Bench0310	Traffic (CEOI11_tra)	C++17	100 / 100	885 ms	90548 KiB

tra

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,limx,limy;
    cin >> n >> m >> limx >> limy;
    vector<int> x(n+1,0);
    vector<int> y(n+1,0);
    for(int i=1;i<=n;i++) cin >> x[i] >> y[i];
    vector<int> v[n+1];
    vector<int> vr[n+1];
    vector<array<int,2>> edges;
    auto add=[&](int a,int b)
    {
        v[a].push_back(b);
        vr[b].push_back(a);
        edges.push_back({a,b});
    };
    for(int i=1;i<=m;i++)
    {
        int a,b,t;
        cin >> a >> b >> t;
        add(a,b);
        if(t==2) add(b,a);
    }
    vector<bool> vis(n+1,0);
    vector<int> ord;
    function<void(int)> dfs1=[&](int a)
    {
        vis[a]=1;
        for(int to:v[a]) if(!vis[to]) dfs1(to);
        ord.push_back(a);
    };
    for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
    reverse(ord.begin(),ord.end());
    int scc_id=0;
    vector<int> scc(n+1,0);
    function<void(int)> dfs2=[&](int a)
    {
        scc[a]=scc_id;
        for(int to:vr[a]) if(scc[to]==0) dfs2(to);
    };
    for(int a:ord)
    {
        if(scc[a]!=0) continue;
        scc_id++;
        dfs2(a);
    }
    vector<int> g[scc_id+1];
    vector<int> gr[scc_id+1];
    for(auto [a,b]:edges)
    {
        if(scc[a]!=scc[b])
        {
            g[scc[a]].push_back(scc[b]);
            gr[scc[b]].push_back(scc[a]);
        }
    }
    vector<bool> is_source(scc_id+1,0);
    for(int i=1;i<=n;i++) if(x[i]==0) is_source[scc[i]]=1;
    vector<int> reach(scc_id+1,-1);
    function<void(int)> dfs3=[&](int a)
    {
        reach[a]=is_source[a];
        for(int to:gr[a])
        {
            if(reach[to]==-1) dfs3(to);
            reach[a]|=reach[to];
        }
    };
    for(int i=1;i<=scc_id;i++) if(reach[i]==-1) dfs3(i);
    vector<int> valid;
    for(int i=1;i<=n;i++)
    {
        if(x[i]==limx&&reach[scc[i]]==1) valid.push_back(y[i]);
    }
    sort(valid.begin(),valid.end());
    vector<array<int,2>> opt(scc_id+1,{-2,-2});
    auto get_union=[&](array<int,2> a,array<int,2> b)->array<int,2>
    {
        if(a[0]==-1) return b;
        if(b[0]==-1) return a;
        return {min(a[0],b[0]),max(a[1],b[1])};
    };
    vector<array<int,2>> ini(scc_id+1,{-1,-1});
    for(int i=1;i<=n;i++)
    {
        if(x[i]==limx)
        {
            if(ini[scc[i]][0]==-1) ini[scc[i]]={y[i],y[i]};
            else
            {
                ini[scc[i]][0]=min(ini[scc[i]][0],y[i]);
                ini[scc[i]][1]=max(ini[scc[i]][1],y[i]);
            }
        }
    }
    function<void(int)> dfs4=[&](int a)
    {
        opt[a]=ini[a];
        for(int to:g[a])
        {
            if(opt[to][0]==-2) dfs4(to);
            opt[a]=get_union(opt[a],opt[to]);
        }
    };
    for(int i=1;i<=scc_id;i++) if(opt[i][0]==-2) dfs4(i);
    vector<array<int,2>> tmp;
    for(int i=1;i<=n;i++) if(x[i]==0) tmp.push_back({y[i],i});
    sort(tmp.begin(),tmp.end(),greater<>());
    auto cnt=[&](int l,int r)->int
    {
        return (upper_bound(valid.begin(),valid.end(),r)-lower_bound(valid.begin(),valid.end(),l));
    };
    for(auto [z,i]:tmp) cout << cnt(opt[scc[i]][0],opt[scc[i]][1]) << "\n";
    return 0;
}

• 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