oj.uz

Submission #683996

# Submission time Handle Problem Language Result Execution time Memory
683996 2023-01-19T23:03:33 Z PoonYaPat One-Way Streets (CEOI17_oneway) C++14
100 / 100
 152 ms 23292 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,k,disc[100001],low[100001],cnt,p[100001][18],val_up[100001],val_down[100001],level[100001];
pii edge[100001];
char ans[100001];
vector<pii> adj[100001];
bool bridge[100001],vis[100001];

void tarjan(int x, int line) {
    disc[x]=low[x]=++cnt;
    for (auto s : adj[x]) {
        if (s.second==line) continue;
        if (disc[s.first]) low[x]=min(low[x],disc[s.first]);
        else {
            tarjan(s.first,s.second);
            low[x]=min(low[x],low[s.first]);
            if (low[s.first]>disc[x]) bridge[s.second]=true;
        }
    }
}

void dfs1(int x, int par) {
    vis[x]=true;
    level[x]=level[par]+1;
    p[x][0]=par;
    for (int i=1; i<=17; ++i) p[x][i]=p[p[x][i-1]][i-1];

    for (auto s : adj[x]) {
        if (vis[s.first]) continue;
        dfs1(s.first,x);
    }
}

int lca(int x, int y) {
    if (level[y]>level[x]) swap(x,y);
    int dif=level[x]-level[y];
    for (int i=0; i<18; ++i) {
        if (dif&(1<<i)) x=p[x][i];
    }

    if (x==y) return x;

    for (int i=17; i>=0; --i) {
        if (p[x][i]!=p[y][i]) {
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}

void dfs2(int x) {
    vis[x]=true;
    for (auto s : adj[x]) {
        if (vis[s.first]) continue;
        dfs2(s.first);
        val_up[x]+=val_up[s.first];
        val_down[x]+=val_down[s.first];

        if (bridge[s.second]) {
            if (val_up[s.first]>0) { //s.first to x
                if (edge[s.second].first==x) ans[s.second]='L';
                else ans[s.second]='R';
            } else if (val_down[s.first]>0) { //x to s.first
                if (edge[s.second].first==x) ans[s.second]='R';
                else ans[s.second]='L';
            } else {
                ans[s.second]='B';
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int a,b; cin>>a>>b;
        adj[a].push_back(pii(b,i));
        adj[b].push_back(pii(a,i));
        edge[i]=pii(a,b);
    }
    for (int i=1; i<=n; ++i) {
        if (!disc[i]) {
            tarjan(i,-1);
            dfs1(i,0);
        }
    }
    int q; cin>>q;
    while (q--) {
        int a,b; cin>>a>>b;
        int LCA=lca(a,b);
        ++val_up[a]; --val_up[LCA];
        ++val_down[b]; --val_down[LCA];


    }
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=n; ++i) {
        if (!vis[i]) dfs2(i);
    }
    for (int i=0; i<m; ++i) {
        if (!ans[i]) cout<<'B';
        else cout<<ans[i];
    }

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2948 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2952 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2948 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2952 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 36 ms 10256 KB Output is correct
12 Correct 47 ms 12308 KB Output is correct
13 Correct 62 ms 14956 KB Output is correct
14 Correct 91 ms 17996 KB Output is correct
15 Correct 121 ms 18804 KB Output is correct
16 Correct 70 ms 17660 KB Output is correct
17 Correct 79 ms 19180 KB Output is correct
18 Correct 75 ms 17676 KB Output is correct
19 Correct 76 ms 20384 KB Output is correct
20 Correct 53 ms 13388 KB Output is correct
21 Correct 46 ms 13176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2948 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2952 KB Output is correct
9 Correct 3 ms 2900 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 36 ms 10256 KB Output is correct
12 Correct 47 ms 12308 KB Output is correct
13 Correct 62 ms 14956 KB Output is correct
14 Correct 91 ms 17996 KB Output is correct
15 Correct 121 ms 18804 KB Output is correct
16 Correct 70 ms 17660 KB Output is correct
17 Correct 79 ms 19180 KB Output is correct
18 Correct 75 ms 17676 KB Output is correct
19 Correct 76 ms 20384 KB Output is correct
20 Correct 53 ms 13388 KB Output is correct
21 Correct 46 ms 13176 KB Output is correct
22 Correct 152 ms 20340 KB Output is correct
23 Correct 147 ms 18808 KB Output is correct
24 Correct 115 ms 18824 KB Output is correct
25 Correct 122 ms 23292 KB Output is correct
26 Correct 118 ms 19976 KB Output is correct
27 Correct 126 ms 18820 KB Output is correct
28 Correct 33 ms 6952 KB Output is correct
29 Correct 94 ms 14208 KB Output is correct
30 Correct 91 ms 14376 KB Output is correct
31 Correct 92 ms 14468 KB Output is correct
32 Correct 102 ms 17740 KB Output is correct