oj.uz

Submission #619522

# Submission time Handle Problem Language Result Execution time Memory
619522 2022-08-02T12:42:36 Z czhang2718 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 243 ms 35512 KB 
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=a; i<=b; i++)
#define sz(x) int(x.size())

const int N=1e5+1, K=18;
int n, m, q;
vector<int> adj[N], adj2[N];
int edge[N][2];
bool vis[N];
bool bridge[N];
int par[N];
set<int> s[N];
char dir[N];
int p[N][K];
int h[N];

void dfs(int x, int prv){
    // e = prv edge
    vis[x]=1;
    for(int e:adj[x]){
        if(e==prv) continue;
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) s[x].insert(k);
    }
    for(int e:adj[x]){
        if(e==prv) continue;
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) continue;
        dfs(k, e);
        if(sz(s[k])>sz(s[x])) swap(s[x], s[k]);
        for(int u:s[k]) s[x].insert(u);
    }
    s[x].erase(x);
    // cout << "s[" << x << "]\n";
    // for(int t:s[x]) cout << t << " ";
    //     cout << "\n";
    if(!sz(s[x]) && prv) bridge[prv]=1;
}

int find(int x){ return par[x]==x?x:par[x]=find(par[x]); }
void join(int x, int y){ par[find(x)]=find(y); }

void dfs2(int x){
    vis[x]=1;
    for(int e:adj[x]){
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(!bridge[e] && !vis[k]){
            join(x,k);
            dfs2(k);
        }
    }
}

void dfs3(int x){
    vis[x]=1;
    rep(i,1,K-1) p[x][i]=p[p[x][i-1]][i-1];
    for(int e:adj2[x]){
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) continue;
        h[k]=h[x]+1;
        p[k][0]=x;
        // cout << "par " << k << " " << x << "\n";
        dfs3(k);
    }
}

int up[N], down[N];

void dfs4(int x, int prv){
    vis[x]=1;
    for(int e:adj2[x]){
        int k=edge[e][0]==x?edge[e][1]:edge[e][0];
        if(vis[k]) continue;
        p[k][0]=x;
        dfs4(k, e);
        up[x]+=up[k];
        down[x]+=down[k];
    }
    assert(!(up[x] && down[x]));
    if(prv){
        if(up[x]) dir[prv]=edge[prv][0]==x?'R':'L';
        if(down[x]) dir[prv]=edge[prv][1]==x?'R':'L';
    }
}

int lca(int u, int v){
    if(h[v]>h[u]) swap(u,v);
    int d=h[u]-h[v];
    rep(k,0,K-1){
        if(d&(1<<k)) u=p[u][k];
    }
    if(u==v) return u;
    for(int k=K-1; k>=0; k--){
        if(p[u][k] && p[u][k]!=p[v][k]){
            u=p[u][k];
            v=p[v][k];
        }
    }
    return p[u][0];
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    rep(i,1,m){
        int u,v; cin >> u >> v;
        if(u==v){
            dir[i]='B'; continue;
        }
        edge[i][0]=u;
        edge[i][1]=v;
        dir[i]='B';
        adj[u].push_back(i);
        adj[v].push_back(i);
    }

    rep(i,1,n){
        par[i]=i;
        if(vis[i]) continue;
        dfs(i, 0);
    }
    rep(i,1,n) vis[i]=0;

    rep(i,1,n){
        if(vis[i]) continue;
        dfs2(i);
    }

    rep(e,1,m){
        // if(bridge[e]) cout << "bridge " << e << '\n';
        int a=find(edge[e][0]);
        int b=find(edge[e][1]);
        edge[e][0]=a;
        edge[e][1]=b;
        if(a!=b) adj2[a].push_back(e), adj2[b].push_back(e);
    }

    rep(i,1,n) vis[i]=0;
    rep(i,1,n){
        if(vis[i]) continue;
        dfs3(i);
    }

    cin >> q;
    while(q--){
        int u,v; cin >> u >> v;
        u=find(u);
        v=find(v);
        if(u==v) continue;
        int a=lca(u,v);
        up[u]++;
        up[a]--;
        down[v]++;
        down[a]--;
        // cout << u << " " << a << " " << v << "\n";
    }

    rep(i,1,n) vis[i]=0;
    rep(i,1,n){
        if(!vis[i]) dfs4(i, 0);
    }

    rep(i,1,m) cout << dir[i];
}
// find bridges
// tree

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9880 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 8 ms 9964 KB Output is correct
8 Correct 7 ms 9864 KB Output is correct
9 Correct 6 ms 9864 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9880 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 8 ms 9964 KB Output is correct
8 Correct 7 ms 9864 KB Output is correct
9 Correct 6 ms 9864 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 100 ms 21596 KB Output is correct
12 Correct 100 ms 23688 KB Output is correct
13 Correct 141 ms 26088 KB Output is correct
14 Correct 127 ms 27892 KB Output is correct
15 Correct 139 ms 28532 KB Output is correct
16 Correct 168 ms 27088 KB Output is correct
17 Correct 132 ms 29656 KB Output is correct
18 Correct 145 ms 27088 KB Output is correct
19 Correct 113 ms 31360 KB Output is correct
20 Correct 85 ms 23384 KB Output is correct
21 Correct 70 ms 22476 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9880 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 8 ms 9964 KB Output is correct
8 Correct 7 ms 9864 KB Output is correct
9 Correct 6 ms 9864 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 100 ms 21596 KB Output is correct
12 Correct 100 ms 23688 KB Output is correct
13 Correct 141 ms 26088 KB Output is correct
14 Correct 127 ms 27892 KB Output is correct
15 Correct 139 ms 28532 KB Output is correct
16 Correct 168 ms 27088 KB Output is correct
17 Correct 132 ms 29656 KB Output is correct
18 Correct 145 ms 27088 KB Output is correct
19 Correct 113 ms 31360 KB Output is correct
20 Correct 85 ms 23384 KB Output is correct
21 Correct 70 ms 22476 KB Output is correct
22 Correct 199 ms 30804 KB Output is correct
23 Correct 224 ms 28128 KB Output is correct
24 Correct 233 ms 28224 KB Output is correct
25 Correct 243 ms 35512 KB Output is correct
26 Correct 209 ms 30060 KB Output is correct
27 Correct 179 ms 28276 KB Output is correct
28 Correct 53 ms 13012 KB Output is correct
29 Correct 116 ms 23748 KB Output is correct
30 Correct 112 ms 24144 KB Output is correct
31 Correct 113 ms 24660 KB Output is correct
32 Correct 153 ms 27316 KB Output is correct