oj.uz

Submission #650962

# Submission time Handle Problem Language Result Execution time Memory
650962 2022-10-16T08:29:53 Z lukadupli Traffic (CEOI11_tra) C++14
100 / 100
 1479 ms 91360 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + 5, MAXM = 9e5 + 5, INF = 0x3f3f3f3f;

int n, m, A, B;

vector<int> adj1[MAXN], adj2[MAXN];

vector<pair<int, int>> lt_list, lt_sort;

vector<pair<int, int>> rt_sort, rt_list;
int rt_code[MAXN];

bool bio[MAXN], erased[MAXN];

int scc[MAXN];
set<int> scc_adj[MAXN];

void dfs4erasing(int node){
    bio[node] = true;

    for(int nxt : adj1[node]){
        if(!bio[nxt]) dfs4erasing(nxt);
    }
}

vector<int> scc_stack;
void scc_dfs1(int node){
    bio[node] = true;

    for(int nxt : adj1[node]){
        if(!bio[nxt] && !erased[nxt]) scc_dfs1(nxt);
    }

    scc_stack.push_back(node);
}

void scc_dfs2(int node, int comp){
    bio[node] = true;
    scc[node] = comp;

    for(int nxt : adj2[node]){
        if(erased[nxt]) continue;

        if(!bio[nxt]) scc_dfs2(nxt, comp);
    }
}

int mini[MAXN], maxi[MAXN];
void minmax_dfs(int scomp){
    bio[scomp] = true;

    for(int nxt : scc_adj[scomp]){
        if(!bio[nxt]) minmax_dfs(nxt);

        mini[scomp] = min(mini[scomp], mini[nxt]);
        maxi[scomp] = max(maxi[scomp], maxi[nxt]);
    }
}

int main(){
    // input

    cin >> n >> m >> A >> B;

    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;

        if(x == 0) lt_list.push_back({y, i});
        else if(x == A) rt_list.push_back({y, i});
    }

    for(int i = 0; i < m; i++){
        int a, b, k;
        cin >> a >> b >> k;

        if(k == 1){
            adj1[a].push_back(b);
            adj2[b].push_back(a);
        }
        else{
            adj1[a].push_back(b);
            adj1[b].push_back(a);

            adj2[a].push_back(b);
            adj2[b].push_back(a);
        }
    }

    // erasing
    for(auto par : lt_list) dfs4erasing(par.second);

    for(auto par : rt_list){
        if(!bio[par.second]) erased[par.second] = true;
    }

    // setting up rt_code

    for(auto par : rt_list){
        if(!erased[par.second]) rt_sort.push_back(par);
    }

    sort(rt_sort.begin(), rt_sort.end());

    for(int i = 0; i < rt_sort.size(); i++) rt_code[rt_sort[i].second] = i + 1;

    // scc
    memset(bio, 0, sizeof bio);

    for(int node = 1; node <= n; node++){
        if(!bio[node] && !erased[node]) scc_dfs1(node);
    }

    reverse(scc_stack.begin(), scc_stack.end());
    memset(bio, 0, sizeof bio);

    int comp = 1;
    for(int node : scc_stack){
        if(!bio[node]){
            scc_dfs2(node, comp);
            comp++;
        }
    }

    // scc_adj i mini-maxi start
    memset(mini, INF, sizeof mini);
    memset(maxi, -1, sizeof maxi);

    for(int node = 1; node <= n; node++){
        if(rt_code[node]){
            mini[scc[node]] = min(mini[scc[node]], rt_code[node]);
            maxi[scc[node]] = max(maxi[scc[node]], rt_code[node]);
        }

        for(auto neigh : adj1[node]){
            if(scc[node] != scc[neigh]) scc_adj[scc[node]].insert(scc[neigh]);
        }
    }

    //dfs po scc-ovima
    memset(bio, 0, sizeof bio);
    for(int scomp = 1; scomp < comp; scomp++){
        if(!bio[scomp]) minmax_dfs(scomp);
    }

    //rjesenje
    for(auto par : lt_list){
        if(!erased[par.second]) lt_sort.push_back(par);
    }

    sort(lt_sort.begin(), lt_sort.end(), [](pair<int, int> a, pair<int, int> b){return a > b;});

    for(auto par : lt_sort){
        int node = par.second;

        if(maxi[scc[node]] == -1) cout << "0\n";
        else cout << maxi[scc[node]] - mini[scc[node]] + 1 << '\n';
    }

    // print
    /*
    for(int i = 1; i <= n; i++){
        cout << i << ": ";
        if(erased[i]) cout << "erased\n";
        else cout << "component " << scc[i] << '\n';
    }
    cout << '\n';

    for(int i = 1; i < comp; i++){
        cout << "Adjacent components to component " << i << ":\n\t";

        for(auto e : scc_adj[i]) cout << e << ' ';
        cout << '\n';
    }
    cout << '\n';

    for(int i = 1; i < comp; i++){
        cout << "Component " << i << ", mini: " << mini[i] << ", maxi: " << maxi[i] << '\n';
    }
    */

    return 0;
}

Compilation message

tra.cpp: In function 'int main()':
tra.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i = 0; i < rt_sort.size(); i++) rt_code[rt_sort[i].second] = i + 1;
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31060 KB Output is correct
2 Correct 17 ms 31052 KB Output is correct
3 Correct 19 ms 31112 KB Output is correct
4 Correct 18 ms 31060 KB Output is correct
5 Correct 17 ms 31060 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31060 KB Output is correct
2 Correct 17 ms 31156 KB Output is correct
3 Correct 17 ms 31032 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31060 KB Output is correct
2 Correct 18 ms 31188 KB Output is correct
3 Correct 20 ms 31188 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31316 KB Output is correct
2 Correct 24 ms 31956 KB Output is correct
3 Correct 24 ms 31692 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 33044 KB Output is correct
2 Correct 132 ms 39272 KB Output is correct
3 Correct 84 ms 35232 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 35924 KB Output is correct
2 Correct 161 ms 41820 KB Output is correct
3 Correct 119 ms 38352 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 41008 KB Output is correct
2 Correct 282 ms 51068 KB Output is correct
3 Correct 361 ms 45772 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 42712 KB Output is correct
2 Correct 255 ms 47932 KB Output is correct
3 Correct 403 ms 46024 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 50420 KB Output is correct
2 Correct 493 ms 62948 KB Output is correct
3 Correct 801 ms 61168 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 59180 KB Output is correct
2 Correct 812 ms 82116 KB Output is correct
3 Correct 823 ms 61976 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1333 ms 63792 KB Output is correct
2 Correct 902 ms 91360 KB Output is correct
3 Correct 1464 ms 68280 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 50892 KB Output is correct
2 Correct 917 ms 86564 KB Output is correct
3 Correct 1251 ms 74552 KB Output is correct
4 Correct 1479 ms 68568 KB Output is correct