Submission #114457

#	Time	Username	Problem	Language	Result	Execution time	Memory
114457		PeppaPig	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	4 ms	2688 KiB

oneway

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;

int n, m, p;
map<pii, int> M;
vector<vector<int> > g(N), cc;
vector<pii> E;

int pre[N], low[N];
bitset<N> br;

void tarjan(int u, int p) {
    static int idx = 0;
    static stack<int> S;

    pre[u] = low[u] = ++idx;
    S.emplace(u);
    for(int v : g[u]) if(v != p) {
        if(!pre[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > pre[u]) {
                if(M.count(pii(u, v))) br[M[pii(u, v)]] = true;
                else br[M[pii(v, u)]] = true;

                cc.emplace_back(vector<int>());
                while(cc.back().empty() || cc.back().back() != v) {
                    cc.back().emplace_back(S.top());
                    S.pop();
                }
            }
        } else low[u] = min(low[u], pre[v]);
    }
    if(u == p) {
        cc.emplace_back(vector<int>());
        while(!S.empty()) {
            cc.back().emplace_back(S.top());
            S.pop();
        }
    }
}

int id[N];

void gen_bbt() {
    g.clear(), M.clear();
    g.emplace_back(vector<int>());
    for(vector<int>& c : cc) {
        g.emplace_back(vector<int>());
        for(int v : c) id[v] = g.size() - 1;
    }
    for(int i = 1, a, b; i <= m; i++) if(br[i]) {
        tie(a, b) = E[i-1];
        M[pii(id[a], id[b])] = i;
        M[pii(id[b], id[a])] = i;
        g[id[a]].emplace_back(id[b]);
        g[id[b]].emplace_back(id[a]);
    }
}

int par[N][18], dep[N];

void dfs(int u, int p) {
    dep[u] = dep[p] + 1, par[u][0] = p;
    for(int i = 1; i <= 17; i++) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]) if(v != p) dfs(v, u);
}

int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 17; ~i; i--) if(dep[par[a][i]] >= dep[b]) a = par[a][i];
    if(a == b) return a;
    for(int i = 17; ~i; i--) if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
    return par[a][0];
}

int orient[N];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, a, b; i <= m; i++) {
        scanf("%d %d", &a, &b);
        M[pii(a, b)] = i;
        E.emplace_back(a, b);
        g[a].emplace_back(b), g[b].emplace_back(a);
    }

    for(int i = 1; i <= n; i++) if(!pre[i]) tarjan(i, i);
    gen_bbt();
    for(int i = 1; i < g.size(); i++) if(!dep[i]) dfs(i, 0);
    
    scanf("%d", &p);
    for(int i = 1, a, b; i <= p; i++) {
        scanf("%d %d", &a, &b);
        a = id[a], b = id[b];
        int l = lca(a, b);
        while(a != l) {
            int eid = M[pii(a, par[a][0])];
            if(orient[eid] != 0) break;
            if(E[eid-1] == pii(a, par[a][0])) orient[eid] = 1;
            else orient[eid] = -1;
            a = par[a][0];
        }
        while(b != l) {
            int eid = M[pii(b, par[b][0])];
            if(orient[eid] != 0) break;
            if(E[eid-1] == pii(b, par[b][0])) orient[eid] = -1;
            else orient[eid] = 1;
            b = par[b][0];
        }
    }
    for(int i = 1; i <= m; i++) {
        if(orient[i] == 0) printf("B");
        else if(orient[i] == -1) printf("R");
        else printf("L");
    }
    printf("\n");

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:97:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < g.size(); i++) if(!dep[i]) dfs(i, 0);
                    ~~^~~~~~~~~~
oneway.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

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