Submission #199361

#	Time	Username	Problem	Language	Result	Execution time	Memory
199361		nvmdava	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	487 ms	57336 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100005
#define MOD 1000000007

vector<int> adj[N];
int v[N], u[N];
int dsu[N];
int dep[N], low[N];
int ans[N];

int find(int x){
    return x == dsu[x] ? x : dsu[x] = find(dsu[x]);
}
void merge(int a, int b){
    dsu[find(a)] = find(b);
}

int proc[N];

void dfs(int v, int p){
    ++proc[v];
    low[v] = dep[v] = dep[::v[p] ^ ::u[p] ^ v] + 1;
    
    for(auto& x : adj[v]){
        if(x == p) continue;
        int u = ::v[x] ^ ::u[x] ^ v;
        if(!dep[u])
            dfs(u, x);
        low[v] = min(low[v], low[u]);
    }
    if(low[v] != dep[v])
        merge(v, ::v[p] ^ ::u[p] ^ v);
}

map<int, int> in[N];

void dfs2(int v, int p){
    ++proc[v];
    for(auto& x : adj[v]){
        if(x == p) continue;
        int u = ::v[x] ^ ::u[x] ^ v;
        dfs2(u, x);
        if(in[v].size() < in[u].size())
            swap(in[v], in[u]);
    }

    for(auto& x : adj[v]){
        if(x == p) continue;
        int u = ::v[x] ^ ::u[x] ^ v;
        for(auto& y : in[u]){
            if((in[v][y.ff] += y.ss) == 3)
                in[v].erase(y.ff);
        }
    }
    if(!in[v].empty()){
        int val = in[v].begin() -> ss - 1;
        if(val ^ (v == ::v[p]) == 1)
            ans[p] = 1;
        else
            ans[p] = 2;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= m; ++i){
        cin>>v[i]>>u[i];
        adj[v[i]].push_back(i);
        adj[u[i]].push_back(i);
    }

    for(int i = 1; i <= n; ++i)
        dsu[i] = i;
    
    for(int i = 1; i <= n; ++i)
        if(proc[i] == 0)
            dfs(i, 0);

    for(int i = 1; i <= n; ++i)
        adj[i].clear();
    for(int i = 1; i <= m; ++i){
        v[i] = find(v[i]);
        u[i] = find(u[i]);
        if(v[i] != u[i]){
            adj[v[i]].push_back(i);
            adj[u[i]].push_back(i);
        }
    }

    int p;
    cin>>p;

    while(p--){
        int a, b;
        cin>>a>>b;
        a = find(a);
        b = find(b);
        if(a != b){
            in[a][p] = 1;
            in[b][p] = 2;
        }
    }

    for(int i = 1; i <= n; ++i)
        if(proc[find(i)] == 1)
            dfs2(find(i), 0);

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

Compilation message (stderr)

oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:62:32: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
         if(val ^ (v == ::v[p]) == 1)
                  ~~~~~~~~~~~~~~^~~~

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