oj.uz

Submission #246813

# Submission time Handle Problem Language Result Execution time Memory
246813 2020-07-10T11:12:51 Z dantoh000 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 382 ms 41204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int p[100005], low[100005], num[100005];
int ct = 1;
int n,m,q;
vector<int> G[100005];
vector<int> _G[200005];
int col[100005];
int brid[100005];
int d[100005];
int P[100005][20];
int U[100005], V[100005];
int ans[100005];
int cct = 1;
vector<ii> hm[100005];
vector<int> ord;
map<ii, int> countedg;
void dfs(int u){
    low[u] = num[u] = ct++;
    for (auto v : G[u]){
        if (num[v] == -1){
            p[v] = u;
            dfs(v);
            if (low[v] > num[u]){
                //printf("%d %d is a bridge\n",u,v);
                brid[v] = 1;
            }
            low[u] = min(low[u],low[v]);
        }
        else if (p[u] != v){
            low[u] = min(low[u],num[v]);
        }
    }
}
void dfs2(int u){
    for (auto v : G[u]){
        if (p[v] == u){
            if (brid[v] && countedg[ii(min(u,v),max(u,v))] == 1) continue;
            col[v] = col[u];
            dfs2(v);
        }
    }
}
void dfs3(int u){
    ord.push_back(u);
    for (auto v : _G[u]){
        if (P[v][0] == -1){
            //printf("%d -> %d\n",u,v);
            P[v][0] = u;
            d[v] = d[u]+1;
            dfs3(v);
        }
    }
}
int lca(int u, int v){
    if (d[u] < d[v]) swap(u,v);
    int dif = d[u]-d[v];
    for (int i = 0; i < 20; i++){
        if (dif>>i&1){
            u = P[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--){
        if (P[u][i] != -1 && P[v][i] != -1 && P[u][i] != P[v][i]){
            u = P[u][i], v = P[v][i];
        }
    }
    assert(P[u][0] == P[v][0]);
    return P[u][0];
}
int main(){
    scanf("%d%d",&n,&m);
    memset(num,-1,sizeof(num));
    for (int i = 0; i < m; i++){
        scanf("%d%d",&U[i],&V[i]);
        int che = ++countedg[ii(min(U[i],V[i]),max(U[i],V[i]))];
        if (U[i] == V[i] || che > 1) continue;
        G[U[i]].push_back(V[i]);
        G[V[i]].push_back(U[i]);
    }
    for (int i = 1; i <= n; i++){
        if (num[i] == -1) dfs(i);
    }
    for (int i = 1; i <= n; i++){
        if (col[i] == 0){
            col[i] = cct++;
            dfs2(i);
        }
    }
    //for (int i = 1; i <= n; i++){ printf("%d ",col[i]); }
    for (int u = 1; u <= n; u++){
        for (auto v : G[u]){
            if (col[v] != col[u]){
                _G[col[u]].push_back(col[v]);
            }
        }
    }
    memset(P,-1,sizeof(P));
    for (int i = 1; i < cct; i++){
        if (P[i][0] == -1){
            P[i][0] = i;
            dfs3(i);
        }
    }
    for (int k = 1; k < 20; k++){
        for (int i = 1; i < cct; i++){
            if (P[i][k-1] == -1) break;
            P[i][k] = P[P[i][k-1]][k-1];
        }
    }
    scanf("%d",&q);
    for (int i = 0; i < q; i++){
        int a, b;
        scanf("%d%d",&a,&b);
        if (col[a] == col[b]) continue;
        else{
            a = col[a];
            b = col[b];
            int c = lca(a,b);
            //printf("%d %d %d\n",a,c,b);
            if (c != a) hm[c].push_back({a,1});
            if (c != b) hm[c].push_back({b,-1});
        }
    }
    for (auto x:  ord){
        for (auto cur : hm[x]){
            int u = cur.first, dir = cur.second;
            while (ans[u] == 0 && u != x){
                //printf("%d -> %d with %d\n",u,P[u][0],dir);
                ans[u] = dir;
                u = P[u][0];
            }
        }
    }
    for (int i = 0; i < m; i++){
        int u = U[i], v = V[i];
        if (col[u] == col[v]){
            printf("B");
        }
        else{
            u = col[u], v = col[v];
            if (d[v] > d[u]){
                if (ans[v] == 1) printf("L");
                else if (ans[v] == -1) printf("R");
                else printf("B");
            }
            else{
                if (ans[u] == 1) printf("R");
                else if (ans[u] == -1) printf("L");
                else printf("B");
            }
        }
    }

}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
oneway.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&U[i],&V[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
oneway.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17920 KB Output is correct
2 Correct 14 ms 17920 KB Output is correct
3 Correct 15 ms 18176 KB Output is correct
4 Correct 15 ms 18176 KB Output is correct
5 Correct 20 ms 18176 KB Output is correct
6 Correct 15 ms 18048 KB Output is correct
7 Correct 16 ms 18176 KB Output is correct
8 Correct 17 ms 18176 KB Output is correct
9 Correct 15 ms 18048 KB Output is correct
10 Correct 15 ms 18048 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17920 KB Output is correct
2 Correct 14 ms 17920 KB Output is correct
3 Correct 15 ms 18176 KB Output is correct
4 Correct 15 ms 18176 KB Output is correct
5 Correct 20 ms 18176 KB Output is correct
6 Correct 15 ms 18048 KB Output is correct
7 Correct 16 ms 18176 KB Output is correct
8 Correct 17 ms 18176 KB Output is correct
9 Correct 15 ms 18048 KB Output is correct
10 Correct 15 ms 18048 KB Output is correct
11 Correct 127 ms 29884 KB Output is correct
12 Correct 150 ms 31112 KB Output is correct
13 Correct 200 ms 32592 KB Output is correct
14 Correct 340 ms 34472 KB Output is correct
15 Correct 207 ms 35060 KB Output is correct
16 Correct 254 ms 35508 KB Output is correct
17 Correct 248 ms 36468 KB Output is correct
18 Correct 235 ms 35568 KB Output is correct
19 Correct 224 ms 37108 KB Output is correct
20 Correct 171 ms 30072 KB Output is correct
21 Correct 134 ms 29304 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 17920 KB Output is correct
2 Correct 14 ms 17920 KB Output is correct
3 Correct 15 ms 18176 KB Output is correct
4 Correct 15 ms 18176 KB Output is correct
5 Correct 20 ms 18176 KB Output is correct
6 Correct 15 ms 18048 KB Output is correct
7 Correct 16 ms 18176 KB Output is correct
8 Correct 17 ms 18176 KB Output is correct
9 Correct 15 ms 18048 KB Output is correct
10 Correct 15 ms 18048 KB Output is correct
11 Correct 127 ms 29884 KB Output is correct
12 Correct 150 ms 31112 KB Output is correct
13 Correct 200 ms 32592 KB Output is correct
14 Correct 340 ms 34472 KB Output is correct
15 Correct 207 ms 35060 KB Output is correct
16 Correct 254 ms 35508 KB Output is correct
17 Correct 248 ms 36468 KB Output is correct
18 Correct 235 ms 35568 KB Output is correct
19 Correct 224 ms 37108 KB Output is correct
20 Correct 171 ms 30072 KB Output is correct
21 Correct 134 ms 29304 KB Output is correct
22 Correct 382 ms 39068 KB Output is correct
23 Correct 344 ms 38348 KB Output is correct
24 Correct 363 ms 38316 KB Output is correct
25 Correct 358 ms 41204 KB Output is correct
26 Correct 342 ms 39384 KB Output is correct
27 Correct 339 ms 38608 KB Output is correct
28 Correct 74 ms 20344 KB Output is correct
29 Correct 212 ms 31728 KB Output is correct
30 Correct 188 ms 31856 KB Output is correct
31 Correct 174 ms 32248 KB Output is correct
32 Correct 285 ms 33648 KB Output is correct