Submission #170827

#	Time	Username	Problem	Language	Result	Execution time	Memory
170827		oolimry	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	6 ms	4984 KiB

oneway

#include <bits/stdc++.h>

using namespace std;


struct node{
    int depth;
    bool vis = false;
    int low;
    int p;
    int up = 0; ///0 - undecided, 1 - up to parent, 2 - down to child
    vector<int> adj;
};


node g1[100005];
typedef pair<int,int> ii;
set<ii> bridges;
void dfs(int u){
    if(g1[u].vis) return;
    g1[u].low = g1[u].depth;
    g1[u].vis = true;
    for(int i = 0;i < g1[u].adj.size();i++){
        int v = g1[u].adj[i];
        if(!g1[v].vis){
            g1[v].depth = g1[u].depth + 1;
            g1[v].p = u;
            dfs(v);
            g1[u].low = min(g1[v].low,g1[u].low);

            if(g1[v].low > g1[u].depth){
                bridges.insert(ii(u,v));
                bridges.insert(ii(v,u));
            }
        }
        else if(g1[u].p != v){
            g1[u].low = min(g1[u].low, g1[v].depth);
        }
    }
}

class UFDS{
public:
    vector<int> rak;
    vector<int> p;
    int n;
    int numSets;

    void create(int nn){
        n = nn;
        numSets = n;
        for(int i = 0;i < n;i++){
            rak.push_back(0);
            p.push_back(i);
        }
    }

    int findSet(int i){
        if(i == p[i]) return i;
        else{
            p[i] = findSet(p[i]);
            return p[i];
        }
    }

    void unionSet(int a, int b){
        int x = findSet(a);
        int y = findSet(b);
        if(x == y) return;
        numSets--;
        if(rak[x] < rak[y]){
            p[x] = y;
        }
        else{
            p[y] = x;
            if(rak[x] == rak[y]) rak[x]++;
        }
    }
};
set<ii> nondupl;
set<ii> duplicates;
vector<pair<ii, int> > edgeIndex;


vector<node> tree;

void root(int u){
    if(tree[u].vis) return;
    tree[u].vis = true;
    for(int i = 0;i < tree[u].adj.size();i++){
        int v = tree[u].adj[i];
        if(tree[v].vis) continue;
        tree[v].depth = tree[u].depth + 1;
        tree[v].p = u;
        root(v);
    }
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
int main()
{
    //freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    
    UFDS overall;
    overall.create(n);
    for(int i = 0;i < m;i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        overall.unionSet(a,b);
        g1[a].adj.push_back(b);
        g1[b].adj.push_back(a);
        if(nondupl.find(ii(a,b)) == nondupl.end()){
            nondupl.insert(ii(a,b));
        }
        else{
            duplicates.insert(ii(a,b));
        }

        if(nondupl.find(ii(b,a)) == nondupl.end()){
            nondupl.insert(ii(b,a));
        }
        else{
            duplicates.insert(ii(b,a));
        }
        edgeIndex.push_back(make_pair(ii(a,b),i));
    }
    
    if(overall.numSets != 1) return 1;

    for(int i = 0;i < n;i++){
        if(!g1[i].vis){
            g1[i].depth = 0;
            dfs(i);
        }
    }

    for(ii x : bridges){
        //cout << x.first << " " << x.second << "\n";
    }

    ///creating the bridge tree
    UFDS ufds;

    ufds.create(n);

    for(int i = 0;i < n;i++){
        for(int j = 0;j < g1[i].adj.size();j++){
            ii x = ii(i, g1[i].adj[j]);
            if(duplicates.find(x) != duplicates.end() || bridges.find(x) == bridges.end()){
                ufds.unionSet(x.first,x.second);
            }
        }
    }

    //cout << ufds.findSet(0) << ufds.findSet(1);
    set<int> coms;

    int id[n];
    fill(id,id+n,-1);
    for(int i = 0;i < n;i++){
        if(coms.find(ufds.findSet(i)) != coms.end()) continue;
        else{
            id[ufds.findSet(i)] = coms.size();
            coms.insert(ufds.findSet(i));
            node kkkk;
            tree.push_back(kkkk);
        }
    }

    for(int i = 0;i < n;i++){
        //cout << id[i] << " ";
    }
    //cout << "\n";

    set<ii> edges;

    for(int i = 0;i < n;i++){
        for(int j = 0;j < g1[i].adj.size();j++){
            int u = i;
            int v = g1[i].adj[j];
            u = id[ufds.findSet(u)];
            v = id[ufds.findSet(v)];
            if(u != v){
                if(v > u) swap(u,v);
                edges.insert(ii(u,v));
            }
        }
    }


    for(ii x : edges){
        //cout << x.first << " " << x.second << "\n";
        tree[x.first].adj.push_back(x.second);
        tree[x.second].adj.push_back(x.first);
    }

    int nn = tree.size();

    for(int i =0;i < nn;i++){
        if(!tree[i].vis){
            //cout << i << "\n";
            tree[i].depth = 0;
            root(i);
        }
    }

    for(int i = 0;i < nn;i++){
        //cout << tree[i].depth << " ";
    }
    //cout << "\n";

    int p = 0;

    cin >> p;
    for(int qq = 0;qq < p;qq++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        a = id[ufds.findSet(a)];
        b = id[ufds.findSet(b)];
        while(a != b){
            if(tree[a].depth > tree[b].depth){
                tree[a].up = 1;
                a = tree[a].p;
            }
            else{
                tree[b].up = 2;
                b = tree[b].p;
            }
        }
    }

    for(int i = 0;i < nn;i++){
        //cout << tree[i].up << " ";
    }
    //cout << "\n";
    //cout << '\n';
    //cout << '\n';
    int ans[n];
    for(int i = 0;i < m;i++){
        ans[i] = 0;
    }
    for(int i = 0;i < m;i++){
        ii x = edgeIndex[i].first;
        int y = edgeIndex[i].second;
        //cout << x.first << " " << x.second << " " << y << "\n";
        if(duplicates.find(x) != duplicates.end() || bridges.find(x) == bridges.end()){
            ans[i] = 4;
            continue;
        }
        else{
            int u = id[ufds.findSet(x.first)];
            int v = id[ufds.findSet(x.second)];
            if(abs(tree[u].depth - tree[v].depth) > 1) return 1;
            //cout << u << " " << v << " ";
            if(tree[u].depth > tree[v].depth){ ///u -> v
                ans[i] = tree[u].up;
                //cout << tree[u].up << " u\n";
            }
            else{ ///v -> u
                ans[i] = 3 - tree[v].up;
                //cout << tree[v].up << " v\n";
            }
        }
    }

    for(int i = 0;i < m;i++){
        //cout << ans[i] << " ";
        if(ans[i] == 1) cout << "R";
        else if(ans[i] == 2) cout << "L";
        else if(ans[i] == 4) cout << "X";
        else cout << "B";
    }


    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int)':
oneway.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < g1[u].adj.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void root(int)':
oneway.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < tree[u].adj.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:153:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
     for(ii x : bridges){
            ^
oneway.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < g1[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~
oneway.cpp:194:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < g1[i].adj.size();j++){
                       ~~^~~~~~~~~~~~~~~~~~
oneway.cpp:262:13: warning: unused variable 'y' [-Wunused-variable]
         int y = edgeIndex[i].second;
             ^

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40