제출 #920343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920343		byunjaewoo	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	147 ms	262144 KiB

oneway

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010;
int N, M, K, cnt, dfsn[Nmax], G[Nmax], ans[Nmax], Dep[Nmax], Par[20][Nmax], X[Nmax], Y[Nmax];
bool chk[Nmax];
vector<pair<int, int>> adj[Nmax], adj2[Nmax];
stack<pair<int, int>> S;
map<pair<int, int>, bool> mp;

int Find(int x) {return G[x]?(G[x]=Find(G[x])):x;}
void Union(int u, int v) {
    u=Find(u), v=Find(v);
    if(u!=v) G[u]=v;
}

int DFS(int curr, int prev) {
    dfsn[curr]=++cnt;
    int ret=cnt;
    for(auto [next, w]:adj[curr]) if(next!=prev) {
        if(dfsn[next]<dfsn[curr]) S.push({curr, next});
        if(dfsn[next]) ret=min(ret, dfsn[next]);
        else {
            int tmp=DFS(next, curr);
            ret=min(ret, tmp);
            if(tmp>=dfsn[curr]) {
                bool flag=false;
                while(!S.empty() && S.top()!=make_pair(curr, next)) {
                    Union(S.top().first, S.top().second);
                    S.pop();
                    flag=true;
                }
                if(flag) Union(S.top().first, S.top().second);
                S.pop();
            }
        }
    }
    return ret;
}

void DFS2(int curr, int prev) {
    chk[curr]=true;
    for(auto [next, w]:adj2[curr]) if(next!=prev) {
        Dep[next]=Dep[curr]+1, Par[0][next]=curr;
        DFS2(next, curr);
    }
}

int LCA(int u, int v) {
    if(Dep[u]<Dep[v]) swap(u, v);
    for(int i=19; i>=0; i--) if(Dep[Par[i][u]]>Dep[v]) u=Par[i][u];
    if(Dep[u]!=Dep[v]) u=Par[0][u];
    for(int i=19; i>=0; i--) if(Par[i][u]!=Par[i][v]) u=Par[i][u], v=Par[i][v];
    if(u!=v) u=Par[0][u];
    return u;
}

/*void Update(int s, int e) {
    int l=LCA(s, e);
    X[s]=-1, X[e]=1;
    Y[l]++;
}*/

void Update(int s, int e) {
    int l=LCA(s, e);
    for(int i=s; i!=l; i=Par[0][i]) {
        int j=Par[0][i], x=0;
        for(auto [k, w]:adj2[j]) if(k==i) x=w;
        if(x>0) ans[x]=-1;
        else ans[-x]=1;
    }
    for(int i=e; i!=l; i=Par[0][i]) {
        int j=Par[0][i], x=0;
        for(auto [k, w]:adj2[j]) if(k==i) x=w;
        if(x>0) ans[x]=1;
        else ans[-x]=-1;
    }
}

int DFS3(int curr, int prev) {
    int a=0, b=0;
    for(auto [next, w]:adj2[curr]) if(next!=prev) {
        int tmp=DFS3(next, curr);
        if(w*tmp>0) ans[abs(w)]=1;
        if(w*tmp<0) ans[abs(w)]=-1;
        if(tmp>0) a++;
        else b++;
    }
    a-=Y[curr], b-=Y[curr];
    if(a) return 1;
    else if(b) return -1;
    else return X[curr];
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1; i<=M; i++) {
        int u, v; cin>>u>>v;
        if(mp[{u, v}]) Union(u, v);
        mp[{u, v}]=mp[{v, u}]=true;
        adj[u].push_back({v, i}); adj[v].push_back({u, -i});
    }
    DFS(1, 0);
    for(int i=1; i<=N; i++) {
        for(auto [j, w]:adj[i]) {
            int u=Find(i), v=Find(j);
            if(u!=v) adj2[u].push_back({v, w});
        }
    }
    for(int i=1; i<=N; i++) if(!chk[i]) DFS2(i, 0);
    for(int i=1; i<20; i++) for(int j=1; j<=N; j++) Par[i][j]=Par[i-1][Par[i-1][j]];
    cin>>K;
    while(K--) {
        int s, e; cin>>s>>e;
        s=Find(s), e=Find(e);
        if(s!=e) Update(s, e);
    }
    // DFS3(1, 0);
    for(int i=1; i<=M; i++) {
        if(!ans[i]) cout<<"B";
        else if(ans[i]>0) cout<<"R";
        else cout<<"L";
    }
    return 0;
}

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