Submission #1268069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268069		Sofiatpc	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	59 ms	22208 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAXN = 1*1e5+5, MAX = 16;
vector< pair<int,int> > adj[MAXN], adj2[MAXN];
vector<int> ponte;
int pai[MAXN], s[MAXN], dist[MAXN], low[MAXN], val[MAXN];
int u[MAXN], v[MAXN], ans[MAXN]; 

int find(int x){
    if(pai[x] == x)return x;
    return pai[x] = find(pai[x]);
}

void merge(int a, int b){
    a = find(a), b = find(b);
    if(a == b)return;
    if(s[a] < s[b])swap(a,b);
    pai[b] = a;
    s[a] += s[b];
}

void dfs(int s, int p){
    low[s] = dist[s];

    int qtd = 0;
    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i].fi, id = adj[s][i].sc;

        if(qtd == 0 && viz == p){qtd++; continue;}
        if(dist[viz])low[s] = min(low[s],low[viz]);
        else{
            dist[viz] = dist[s]+1;
            dfs(viz,s);
            low[s] = min(low[s],low[viz]);

            if(low[viz] <= dist[s])merge(s,viz);
            else ponte.push_back(id);
        }
    }
}

void dfs2(int s,int p){
    dist[s] = 1;

    for(int i = 0; i < sz(adj2[s]); i++){
        int viz = adj2[s][i].fi, id = adj2[s][i].sc;
        if(viz == p)continue;

        dfs2(viz,s);
        if(val[viz] < 0){
            if(u[id] == s)ans[id] = 1;
            else ans[id] = 2;
        }
        if(val[viz] > 0){
            if(u[id] == s)ans[id] = 2;
            else ans[id] = 1;
        }
        
        val[s] += val[viz];
    }
    
}

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

    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; i++){
        pai[i] = i; s[i] = 1;
    }

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

    for(int i = 1; i <= n; i++)
        if(dist[i] == 0){
            dist[i] = 1;
            dfs(i,0);
        }

    for(int i = 0; i < sz(ponte); i++){
        u[ponte[i]] = find(u[ponte[i]]), v[ponte[i]] = find(v[ponte[i]]);
        adj2[u[ponte[i]]].emplace_back(v[ponte[i]],ponte[i]);
        adj2[v[ponte[i]]].emplace_back(u[ponte[i]],ponte[i]);
    }

    int q; cin>>q;
    while(q--){
        int a,b; cin>>a>>b;

        val[find(a)]++; val[find(b)]--;
    }

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

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

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