Submission #650962

#	Time	Username	Problem	Language	Result	Execution time	Memory
650962		lukadupli	Traffic (CEOI11_tra)	C++14	100 / 100	1479 ms	91360 KiB

tra

#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 (stderr)

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 / 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