Submission #116083

#	Time	Username	Problem	Language	Result	Execution time	Memory
116083		Meloric	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	233 ms	15860 KiB

oneway

#include <bits/stdc++.h>
#define pb push_back
#define X first
#define Y second
#define pii pair<int, int>

using namespace std;
vector<vector<int>> g;
struct edge{
    int u, v;
    char dir;
};
vector<edge> ed;
vector<int> tin, low, val, vis;
int n, m, counter;

void dfs(int v, int p){
    tin[v] = low[v] = counter;
    counter++;
    vis[v] = 1;
    for(auto ch : g[v]){
        if(ch == p)continue;
        int nx = (v==ed[ch].u) ? ed[ch].v : ed[ch].u;
        if(vis[nx]){
            low[v] = min(low[v], tin[nx]);
            continue;
        }
        dfs(nx, ch);
        low[v] = min(low[v], low[nx]);
        pii cor;
        if(tin[v] < low[nx]){
            if(val[nx] == 0)continue;
            if(val[nx] < 0){
                cor = {v, nx};
            }else{
                cor = {nx, v};
            }
            if(ed[ch].u == cor.X)ed[ch].dir = 'R';
            else ed[ch].dir = 'L';
        }
        val[v]+=val[nx];
    }
}
int main(){
    cin >> n >> m;
    counter = 0;
    g.assign(n, vector<int>());
    tin.assign(n, 0);
    low.assign(n, 0);
    val.assign(n, 0);
    vis.assign(n, 0);
    for(int i = 0; i< m; i++){
        int c, d; cin >> c >> d; c--; d--;
        ed.pb({c, d, 'B'});
        g[c].pb(i); g[d].pb(i);
    }
    int q; cin >> q;
    while(q--){
        int c, d; cin >> c >> d; c--; d--;
        val[c]++; val[d]--;
    }
    for(int i = 0;i<n; i++){
        if(!vis[i])dfs(i, -1);
    }
    for(auto i : ed){
        cout << i.dir;
    }
    return 0;
}

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