Submission #771512

#	Time	Username	Problem	Language	Result	Execution time	Memory
771512		PoonYaPat	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	2644 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,mark1[100001],mark2[100001],dis[100001],edge[100001],k[100001],root;
vector<pii> adj[100001];
pii ed[100001];
bool vis[100001];
string ans;

void dfs(int x, int par) {
    vis[x]=true;
    for (auto s : adj[x]) {
        if (s.first==par) continue;
        if (vis[s.first]) {
            ++mark2[x];
            --mark2[s.first];
            ans[s.second]='B';
        } else {
            edge[s.first]=s.second;
            dfs(s.first,x);
            mark2[x]+=mark2[s.first];
            mark1[x]+=mark1[s.first];
        }
    }

    if (x==root) return; 
    if (mark2[x]) ans[edge[x]]='B';
    else {
        if (mark1[x]>0) {
            if (ed[edge[x]].first==x) ans[edge[x]]='R';
            else ans[edge[x]]='L';
        } else if (mark1[x]<0) {
            if (ed[edge[x]].first==x) ans[edge[x]]='L';
            else ans[edge[x]]='R';
        } else {
            ans[edge[x]]='B';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int a,b; cin>>a>>b;
        ans+=" ";
        adj[a].push_back(pii(b,i));
        adj[b].push_back(pii(a,i));
        ed[i]=pii(a,b);
    }
    int k; cin>>k;
    while (k--) {
        int a,b; cin>>a>>b;
        mark1[a]++;
        mark1[b]--;
    }

    for (int i=1; i<=n; ++i) {
        if (!vis[i]) {
            root=i;
            dfs(root,0);
        }
    }
    cout<<ans;
}

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