Submission #35491

#	Time	Username	Problem	Language	Result	Execution time	Memory
35491		imaxblue	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	769 ms	44788 KiB

oneway

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int> 
#define pb push_back
#define x first
#define y second
#define lb lower_bound
#define mp make_pair
int n, m, p, com[100005], pre[100005], num[100005], c, a, b;
int par[20][100005], d[100005], one[100005], dir[100005];
vector<pii> st[100005];
vector<pii> v[100005], w[100005];
vector<int> vis;
void dfs(int N, int P){
    if (num[N]!=0) return;
    num[N]=(pre[N]=++c);
    //if (num[N]==1) exit(2);
    vis.pb(N);
    for (int l=0; l<v[N].size(); ++l){
        if (v[N][l].x==P) {P=-1; continue;}
        dfs(v[N][l].x, N);
        pre[N]=min(pre[N], pre[v[N][l].x]);
    }
    if (pre[N]==num[N]){
        int t=-1;
        do{
            t=vis.back(); vis.pop_back();
            com[t]=N;
            //cout << N << ' ' << t << endl;
            for (int l=0; l<v[t].size(); ++l){
                w[N].pb(v[t][l]);
            }
        } while(t!=N);
    }
}
void dfs2(int N, int P){
    N=com[N];
    if (P==-1) d[N]=1; else d[N]=d[P]+1;
    for (int l=0; l<20; ++l) par[l][N]=-1;
    par[0][N]=P;
    int k=0;
    while(par[k][N]!=-1){
        par[k+1][N]=par[k][par[k][N]]; ++k;
    }
    for (int l=0; l<w[N].size(); ++l){
        w[N][l].x=com[w[N][l].x];
        if (w[N][l].x==N || w[N][l].x==P) continue;
        dfs2(w[N][l].x, N);
    }
}
void lca(int a, int b){
    int A=(a=com[a]), B=(b=com[b]), k=19;
    if (a==b) return;
    while(d[A]>d[B]){
        //cout << A << ' ' << d[A] << endl;
        while(k>0 && (d[A]-(1 << k)<d[B])) k--;
        A=par[k][A];
    }
    while(d[B]>d[A]){
        //cout << B << ' ' << d[B] << endl;
        while(k>0 && (d[B]-(1 << k)<d[A])) k--;
        B=par[k][B];
    }
    k=19;
    while(A!=B){
        while(k>0 && par[k][A]==par[k][B]){
            --k;
        }
        A=par[k][A]; B=par[k][B];
        //cout << k << ' ' << A << ' ' << B << endl;
    }
    //cout << A << ' ' <<B << endl;return;
    st[a].pb(mp(A, 1));
    st[b].pb(mp(A, 0));
    //cout << a << ' ' << A << ' ' << b << endl;
}
multiset<int> s[2];
void dfs3(int N, int P){
    N=com[N]; com[N]=0;
    for (int l=0; l<st[N].size(); ++l){
        s[st[N][l].y].insert(st[N][l].x);
    }
    //cout << N << ' ' << s[0].size()<< ' ' << s[1].size() << endl;
    int a, b, t;
    for (int l=0; l<w[N].size(); ++l){
        if (w[N][l].x==N || w[N][l].x==P) continue;
        a=s[0].size(); b=s[1].size();
        dfs3(w[N][l].x, N);
        t=0;
        //if (s[0].size()>a && s[1].size()>b) exit(1);
        if (s[0].size()>a) t=1;
        if (s[1].size()>b) t=2;
        if (w[N][l].y<0){
            t=(3-t)%3; w[N][l].y*=-1;
        }
        //cout << N << ' ' << w[N][l].x << ' ' << P << ' ' << t << ' ' << w[N][l].y << endl;
        dir[w[N][l].y]=t;
    }
    s[0].erase(N); s[1].erase(N);
}
int dist[100005][2], r[100005];
queue<pii> q; 
bool dfs4(int N, int P, int D){
    N=com[N]; num[N]=0;
    if (N==D) return 1;
    for (int l=0; l<w[N].size(); ++l){
        w[N][l].x=com[w[N][l].x];
        if (w[N][l].x==P || w[N][l].x==N) continue;
        if (dfs4(w[N][l].x, N, D)){
            //cout << N << ' ' << w[N][l].x << endl;
            dir[abs(w[N][l].y)]=(w[N][l].y<0)+1;
            //cout << "*" << endl;
            return 1;
        }
    }
    return 0;
}
void bfs(int A, int B){
    dfs4(com[A], -1, com[B]);
}
int main() {
    cin >> n >> m;
    for (int l=0; l<m; ++l){
        cin >> a >> b;
        v[a].pb(mp(b, l+1)); v[b].pb(mp(a, -l-1));
    }
    for (int l=1; l<=n; ++l)
        if (num[l]==0)
            dfs(l, -1);
    cin >> p;
    if (p<=100 && 0){
        for (int l=0; l<p; ++l){
            cin >> a >> b;
            bfs(a, b);
        }
    } else {
        
    for (int l=1; l<=n; ++l)
        if (par[0][com[l]]==0)
            dfs2(com[l], -1);
        for (int l=0; l<p; ++l){
            cin >> a >> b;
            lca(a, b);
        }
    for (int l=1; l<=n; ++l)
        if (num[com[l]]!=0)
            dfs3(com[l], -1);
    }
    for (int l=1; l<=m; ++l){
        if (dir[l]==0) cout << "B";
        else if (dir[l]==1) cout << "R";
        else if (dir[l]==2) cout << "L";
        else return 1;
    }
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<v[N].size(); ++l){
                    ^
oneway.cpp:31:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int l=0; l<v[t].size(); ++l){
                            ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<st[N].size(); ++l){
                    ^
oneway.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^
oneway.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s[0].size()>a) t=1;
                        ^
oneway.cpp:93:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s[1].size()>b) t=2;
                        ^
oneway.cpp: In function 'bool dfs4(int, int, int)':
oneway.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^

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