Submission #1005180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005180		emad234	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	0 ms	348 KiB

oneway

#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const ll mxN = 1e5 + 5;
const ll mod = 1e9 + 7;
using namespace std;
struct edge{
    int first,id,second;
};
vector<vector<edge>>v,tr;
int p[mxN];
int ans[mxN];
bool vis[mxN];
int dep[mxN];
void calctr(int u){
    vis[u] = 1;
    for(auto x : v[u]){
        if(vis[x.F]) continue;
        tr[x.F].push_back({u,x.id,!x.S});
        tr[u].push_back(x);
        calctr(x.F);
    }
}
int n,m,pr;
int g[mxN],t[mxN];
int ng,nt;
void dfs(int u,int par,int ty,int id){
    dep[u] = dep[par] + 1;
    for(auto x : tr[u]){
        if(x.F == par) continue;
        dfs(x.F,u,x.S,x.id);
    }
    if(g[u]){
        if(vis[g[u]]) nt--;
        else ng++;
    }
    if(t[u]){
        if(vis[t[u]]) ng--;
        else nt++;
    } 
    // cout<<nt<<' '<<ng<<'\n';
    vis[u] = 1;
    if(p[u] == 0) p[u] = m;
    for(auto x : v[u]) if(x.F != par) p[u] = min(dep[x.F],p[u]);
    p[par] = p[u];
    // cout<<u<<' '<<p[u]<<'\n';
    if(p[u] >= dep[u]){
        if(ng) ans[id] = ty + 1;
        else if(nt) ans[id] = (!ty) + 1;
    }

}
signed main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    cin >>n>>m;
    v.resize(n + 4);
    tr.resize(n + 4);
    for(int i = 1;i <= m;i++){
        int x,y;
        cin >>x>>y;
        v[x].push_back({y,i, 0});
        v[y].push_back({x,i, 1});
    }
    cin >>pr;
    for(int i = 0;i < pr;i++){
        int x,y;
        cin >>x>>y;
        g[x] = y;
        t[y] = x;
    }
    calctr(1);
    // cout<<"TEST\n";
    memset(vis,0,sizeof vis);
    dfs(1,0,0,0);
    for(int i = 1;i <= m;i++) cout<<(ans[i] == 0 ? 'B' : (ans[i] == 2 ? 'R' : 'L'));

}

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