Submission #255412

#	Time	Username	Problem	Language	Result	Execution time	Memory
255412		giorgikob	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	284 ms	22776 KiB

oneway

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;

const int N = 1e5 + 5;

int n,m,p;
int x,y;
int P[N][21];
vector<pair<int,int>>gr[N];
pair<int,int> edge[N];
char answer[N];
int in[N], out[N];
int timer, root;
vector<int> roots;
int A[N], B[N], fix[N], fixA[N], fixB[N], lvl[N], dp[N];

void dfs(int x,int par,int pp){

        timer++;
        in[x] = timer;
        P[x][0] = pp;
        for(int i = 1; i <= 20; i++){
                P[x][i] = P[P[x][i-1]][i-1];
        }

        fix[x] = 1;
        for(auto p : gr[x]){
                int to = p.ff;
                int ind = p.ss;
                if(!lvl[to]){
                        lvl[to] = lvl[x] + 1;
                        dfs(to,ind,x);
                        dp[x] += dp[to];
                        continue;
                }
                if(ind == par) continue;
                if(lvl[to] < lvl[x]){
                        dp[x]++;
                } else {
                        dp[x]--;
                }
        }

        out[x] = timer;
}

inline bool check(int x,int y){
        return in[x] <= in[y] && out[x] >= out[y];
}

inline int lca(int x,int y){

        if(check(x,y)) return x;
        if(check(y,x)) return y;

        for(int i = 20; i >= 0; i--){
                if(P[x][i] && !check(P[x][i],y)){
                        x = P[x][i];
                }
        }

        return P[x][0];
}

void dfsA(int x,int ind){

        fixA[x] = 1;
        for(auto p : gr[x]){
                int to = p.ff;
                int ind = p.ss;
                if(fixA[to]) continue;
                dfsA(to,ind);
                A[x] += A[to];
        }

        if(A[x] && dp[x] == 0){
                if(edge[ind].ff == x) answer[ind] = 'R'; else answer[ind] = 'L';
        }
}

void dfsB(int x,int ind){

        fixB[x] = 1;
        for(auto p : gr[x]){
                int to = p.ff;
                int ind = p.ss;
                if(fixB[to]) continue;
                dfsB(to,ind);
                B[x] += B[to];
        }

        if(B[x] && dp[x] == 0){
                if(edge[ind].ff == x) answer[ind] = 'L'; else answer[ind] = 'R';
        }
}

int main(){

        cin >> n >> m;
        for(int i = 1; i <= m; i++){
                int x,y;
                cin >> x >> y;
                edge[i] = {x,y};
                gr[x].pb({y,i});
                gr[y].pb({x,i});
        }

        for(int i = 1; i <= n; i++){
                if(fix[i]) continue;
                root = i; lvl[i] = 1;
                roots.pb(root);
                dfs(i,0,0);
        }

        cin >> p;
        while(p--){
                int x,y;
                cin >> x >> y;
                int z = lca(x,y);
                A[x] ++; A[z] --;
                B[y] ++; B[z] --;
        }

        for(int i = 1; i <= m; i++) answer[i] = 'B';

        for(auto root : roots){
                dfsA(root, 0);
        }


        for(auto root : roots){
                dfsB(root, 0);
        }

        for(int i = 1; i <= m; i++){
                cout << answer[i] ;
        }

        cout << endl;
}

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