oj.uz

답안 #494969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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