Submission #494969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
494969	2021-12-17T18:19:08 Z	Bench0310	Traffic (CEOI11_tra)	C++17	100 / 100	885 ms	90548 KB

#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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	1 ms	312 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	464 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	976 KB	Output is correct
2	Correct	5 ms	1604 KB	Output is correct
3	Correct	4 ms	1220 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	7044 KB	Output is correct
2	Correct	77 ms	14400 KB	Output is correct
3	Correct	33 ms	7016 KB	Output is correct

Subtask #6
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	10428 KB	Output is correct
2	Correct	69 ms	17584 KB	Output is correct
3	Correct	44 ms	13976 KB	Output is correct

Subtask #7
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	21692 KB	Output is correct
2	Correct	174 ms	32024 KB	Output is correct
3	Correct	221 ms	24820 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	170 ms	21544 KB	Output is correct
2	Correct	147 ms	28452 KB	Output is correct
3	Correct	227 ms	25320 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	235 ms	39096 KB	Output is correct
2	Correct	314 ms	54832 KB	Output is correct
3	Correct	527 ms	48148 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	65896 KB	Output is correct
2	Correct	567 ms	85936 KB	Output is correct
3	Correct	524 ms	56064 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	829 ms	70452 KB	Output is correct
2	Correct	632 ms	89076 KB	Output is correct
3	Correct	873 ms	76316 KB	Output is correct

Subtask #12
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	228 ms	58308 KB	Output is correct
2	Correct	629 ms	90548 KB	Output is correct
3	Correct	819 ms	76456 KB	Output is correct
4	Correct	885 ms	79764 KB	Output is correct

Submission #494969

Compilation message