oj.uz

Submission #114690

# Submission time Handle Problem Language Result Execution time Memory
114690 2019-06-02T10:39:05 Z PeppaPig One-Way Streets (CEOI17_oneway) C++14
0 / 100
 5 ms 3200 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int dsu[N];

int find(int x) { return dsu[x] = x == dsu[x] ? x : find(dsu[x]); }

int n, m, p;
int a[N], b[N];
vector<int> g[N];

int pre[N], low[N];
bitset<N> br;

void tarjan(int u, int p) {
    static int idx = 0;
    pre[u] = low[u] = ++idx;
    for(int i : g[u]) {
        int v = a[i] ^ b[i] ^ u;
        if(v == p) continue;
        if(!pre[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > pre[u]) br[i] = true;
        } else low[u] = min(low[u], pre[v]);
    }
}

int dp[N], dep[N];

void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    for(int i : g[u]) {
        int v = find(a[i]) ^ find(b[i]) ^ u;
        if(dep[v]) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
}

int main() {
    iota(dsu, dsu+N, 0);

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d", a+i, b+i);
        g[a[i]].emplace_back(i);
        g[b[i]].emplace_back(i);
    }

    for(int i = 1; i <= n; i++) if(!pre[i]) tarjan(i, i); 
    for(int i = 1; i <= m; i++) if(!br[i]) dsu[find(a[i])] = find(b[i]);
    for(int i = 1; i <= n; i++) g[i].clear();
    for(int i = 1; i <= m; i++) if(br[i]) {
        g[find(a[i])].emplace_back(i);
        g[find(b[i])].emplace_back(i);
    }
    
    scanf("%d", &p);
    for(int i = 1, x, y; i <= p; i++) {
        scanf("%d %d", &x, &y);
        ++dp[find(x)], --dp[find(y)];
    }
    for(int i = 1; i <= n; i++) if(!dep[find(i)]) dfs(find(i), find(i));
    for(int i = 1; i <= m; i++) {
        if(!br[i]) printf("B");
        else {
            int u = dep[find(a[i])] > dep[find(b[i])] ? a[i] : b[i];
            if(dp[find(u)] == 0) printf("B");
            else if((dp[find(u)] > 0) == (u == a[i])) printf("R");
            else printf("L");
        } 
    }
    printf("\n");

    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:47: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:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", a+i, b+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~
oneway.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3072 KB Output is correct
2 Correct 4 ms 3072 KB Output is correct
3 Correct 5 ms 3200 KB Output is correct
4 Correct 5 ms 3072 KB Output is correct
5 Correct 5 ms 3200 KB Output is correct
6 Correct 5 ms 3200 KB Output is correct
7 Correct 5 ms 3200 KB Output is correct
8 Correct 5 ms 3072 KB Output is correct
9 Incorrect 5 ms 3200 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3072 KB Output is correct
2 Correct 4 ms 3072 KB Output is correct
3 Correct 5 ms 3200 KB Output is correct
4 Correct 5 ms 3072 KB Output is correct
5 Correct 5 ms 3200 KB Output is correct
6 Correct 5 ms 3200 KB Output is correct
7 Correct 5 ms 3200 KB Output is correct
8 Correct 5 ms 3072 KB Output is correct
9 Incorrect 5 ms 3200 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3072 KB Output is correct
2 Correct 4 ms 3072 KB Output is correct
3 Correct 5 ms 3200 KB Output is correct
4 Correct 5 ms 3072 KB Output is correct
5 Correct 5 ms 3200 KB Output is correct
6 Correct 5 ms 3200 KB Output is correct
7 Correct 5 ms 3200 KB Output is correct
8 Correct 5 ms 3072 KB Output is correct
9 Incorrect 5 ms 3200 KB Output isn't correct
10 Halted 0 ms 0 KB -