Submission #116299

#	Time	Username	Problem	Language	Result	Execution time	Memory
116299		JohnTitor	One-Way Streets (CEOI17_oneway)	C++11	30 / 100	3030 ms	19484 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "OneWay"
int n, m, q;
class edge{
public:
    int u, v, x;
    void input(){
        read(u);
        read(v);
        x=u^v;
    }
    int get_v(int u){
        return x^u;
    }
} e[100001];
char ans[100001];
vector <int> g[100001];
bool done[100001];
int p[100001];
int cnt=0;
int num[100001];
int low[100001];
bool b[100001];
int cp[100001];
int pc[100001];
int h[100001];
int f[100001][20];
void dfs(int u){
    cnt++;
    num[u]=low[u]=cnt;
    for(int i: g[u]) if(done[i]) p[u]=i;
    for(int i: g[u]) if(!done[i]){
        done[i]=1;
        int v=e[i].get_v(u);
        if(num[v]) low[u]=min(low[u], num[v]);
        else{
            dfs(v);
            low[u]=min(low[u], low[v]);
        }
    }

    for(int i: g[u]){
        int v=e[i].get_v(u);
        if(p[v]==i) if(low[v]>num[u]) b[i]=1;
    }
}
int r[100001];
int root(int u){
    if(r[u]<0) return u;
    return r[u]=root(r[u]);
}
void unite(int u, int v){
    u=root(u);
    v=root(v);
    if(u==v) return;
    if(r[u]>r[v]) swap(u, v);
    r[u]+=r[v];
    r[v]=u;
}
void dfslca(int u){
    done[u]=1;
    for(int i=0; f[f[u][i]][i]; i++) f[u][i+1]=f[f[u][i]][i];
    for(int i: g[u]){
        int v=e[i].get_v(u);
        if(done[v]) continue;
        p[v]=i;
        f[v][0]=u;
        h[v]=h[u]+1;
        dfslca(v);
    }
}
int lca(int u, int v){
    if(h[u]<h[v]) swap(u, v);
    DFOR(i, __lg(h[u]), 0) if(h[f[u][i]]>=h[v]) u=f[u][i];
    if(u==v) return u;
    DFOR(i, __lg(h[u]), 0) if(f[u][i]!=f[v][i]){
        u=f[u][i];
        v=f[v][i];
    }
    return f[u][0];
}
void dfstree(int u){
    for(int i: g[u]){
        int v=e[i].get_v(u);
        if(p[v]!=i) continue;
        dfstree(v);
        pc[u]=max(pc[u], pc[v]-1);
        cp[u]=max(cp[u], cp[v]-1);
    }
    if(pc[u]){
        assert(cp[u]==0);
        ans[p[u]]="RL"[u==e[p[u]].u];
    }
    else if(cp[u]){
        ans[p[u]]="LR"[u==e[p[u]].u];
    }
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(m);
    FOR(i, 1, m) ans[i]='B';
    FOR(i, 1, m){
        e[i].input();
        if(e[i].x){
            g[e[i].u].pb(i);
            g[e[i].v].pb(i);
        }
    }
    FOR(i, 1, n) if(!num[i]) dfs(i);
    FOR(i, 1, n) r[i]=-1;
    FOR(i, 1, m) if(!b[i]) unite(e[i].u, e[i].v);
    FOR(i, 1, n) g[i].clear();
    FOR(i, 1, m){
        e[i].u=root(e[i].u);
        e[i].v=root(e[i].v);
        e[i].x=e[i].u^e[i].v;
        if(e[i].x){
            g[e[i].u].pb(i);
            g[e[i].v].pb(i);
        }
    }
    FOR(i, 1, n) done[i]=0;
    FOR(i, 1, n) if((i==root(i))&&(!done[i])){
        p[i]=0;
        h[i]=1;
        dfslca(i);
    }
    read(q);
    {
        int u, v;
        FOR(i, 1, q){
            read(u);
            read(v);
            u=root(u);
            v=root(v);
            int r=lca(u, v);
            cp[u]=max(cp[u], h[u]-h[r]);
            pc[v]=max(pc[v], h[v]-h[r]);
        }
    }
    FOR(i, 1, n) if(i==root(i)) dfstree(i);
    FOR(i, 1, m) putchar(ans[i]);
}

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