oj.uz

Submission #390287

# Submission time Handle Problem Language Result Execution time Memory
390287 2021-04-15T19:06:05 Z mchang One-Way Streets (CEOI17_oneway) C++11
100 / 100
 112 ms 19496 KB 
#define pb push_back
#define eb emplace_back
#define F first
#define S second

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;


vector<pii> adj[1<<18];
char dir[1<<18];
vector<pii> edges;

int pre[1<<18];
int link[1<<18];
int prenum = 1;

int N,M,P;
int indeg[1<<18];
int outdeg[1<<18];

void dfs(int u, int pi) {
    pre[u] = link[u] = prenum++;
    int minlink = pre[u];

    for (auto& e : adj[u]) {
        if (e.S == pi) continue;
        int v = e.F;

        if (pre[v] == 0) {
            dfs(v, e.S);
            indeg[u]+=indeg[v];
            outdeg[u]+=outdeg[v];
        }

        minlink = min(minlink, link[v]);
    }
    link[u] = minlink;

    int deg = outdeg[u]-indeg[u];

    // if parent edge is part of a bcc,
    // we don’t care about direction of that edge
    // we just need to direct bridges
    if (link[u] != pre[u]) return;

    if (deg < 0) {
        // need more coming in from above
        // pi needs to go from parent->u
        if (edges[pi].S == u) dir[pi] = 'R';
        else dir[pi] = 'L';

    } else if (deg > 0) {
        // there are nodes above me that need me
        // need to go from u->parent
        if (edges[pi].F == u) dir[pi] = 'R';
        else dir[pi] = 'L';
    }
}



int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        adj[u].eb(v, i);
        adj[v].eb(u, i);
        dir[i] = 'B';
        edges.eb(u,v);
    }

    scanf("%d", &P);
    for (int i = 0; i < P; i++) {
        int u,v; scanf("%d %d", &u, &v);
        outdeg[u]++;
        indeg[v]++;
    }

    for (int u = 1; u <= N; u++) {
        if (pre[u] == 0) {
            dfs(u, -1);
        }
    }

    for (int i = 0; i < M; i++) {
        printf("%c", dir[i]);
    }

}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%d", &P);
      |     ~~~~~^~~~~~~~~~
oneway.cpp:79:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         int u,v; scanf("%d %d", &u, &v);
      |                  ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6476 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 5 ms 6476 KB Output is correct
8 Correct 5 ms 6552 KB Output is correct
9 Correct 4 ms 6476 KB Output is correct
10 Correct 4 ms 6476 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6476 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 5 ms 6476 KB Output is correct
8 Correct 5 ms 6552 KB Output is correct
9 Correct 4 ms 6476 KB Output is correct
10 Correct 4 ms 6476 KB Output is correct
11 Correct 49 ms 12728 KB Output is correct
12 Correct 54 ms 13636 KB Output is correct
13 Correct 60 ms 14828 KB Output is correct
14 Correct 68 ms 15544 KB Output is correct
15 Correct 71 ms 15664 KB Output is correct
16 Correct 72 ms 13856 KB Output is correct
17 Correct 65 ms 15420 KB Output is correct
18 Correct 68 ms 13920 KB Output is correct
19 Correct 60 ms 16512 KB Output is correct
20 Correct 57 ms 13364 KB Output is correct
21 Correct 52 ms 13112 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 4 ms 6476 KB Output is correct
3 Correct 5 ms 6476 KB Output is correct
4 Correct 5 ms 6476 KB Output is correct
5 Correct 5 ms 6476 KB Output is correct
6 Correct 4 ms 6484 KB Output is correct
7 Correct 5 ms 6476 KB Output is correct
8 Correct 5 ms 6552 KB Output is correct
9 Correct 4 ms 6476 KB Output is correct
10 Correct 4 ms 6476 KB Output is correct
11 Correct 49 ms 12728 KB Output is correct
12 Correct 54 ms 13636 KB Output is correct
13 Correct 60 ms 14828 KB Output is correct
14 Correct 68 ms 15544 KB Output is correct
15 Correct 71 ms 15664 KB Output is correct
16 Correct 72 ms 13856 KB Output is correct
17 Correct 65 ms 15420 KB Output is correct
18 Correct 68 ms 13920 KB Output is correct
19 Correct 60 ms 16512 KB Output is correct
20 Correct 57 ms 13364 KB Output is correct
21 Correct 52 ms 13112 KB Output is correct
22 Correct 88 ms 16492 KB Output is correct
23 Correct 86 ms 14904 KB Output is correct
24 Correct 92 ms 15036 KB Output is correct
25 Correct 85 ms 19496 KB Output is correct
26 Correct 87 ms 16308 KB Output is correct
27 Correct 112 ms 15028 KB Output is correct
28 Correct 51 ms 10680 KB Output is correct
29 Correct 78 ms 14044 KB Output is correct
30 Correct 76 ms 14184 KB Output is correct
31 Correct 78 ms 14520 KB Output is correct
32 Correct 76 ms 16448 KB Output is correct