oj.uz

Submission #56066

# Submission time Handle Problem Language Result Execution time Memory
56066 2018-07-09T18:16:54 Z gabrielsimoes One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 26936 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

const int MAXN = 1e5+10;

int n, m, p;
vector<pii> edges;
vector<pii> requirements;
vector<int> gix[MAXN];

bool isFirst(int cur, int edge) {
    return cur == edges[edge].first;
}

int other(int cur, int edge) {
    if (isFirst(cur, edge)) return edges[edge].second;
    else return edges[edge].first;
}

bool isPartOfCycle[MAXN];
bool edgeUsed[MAXN];
int status[MAXN];
vector<pii> stk;
void dfsCycles(int cur, int inIx) {
    status[cur] = 1;
    stk.push_back({cur, inIx});

    for (int ix : gix[cur]) {
        if (edgeUsed[ix]) continue;
        edgeUsed[ix] = true;

        int nx = other(cur, ix);

        if (status[nx] == 0) {
            dfsCycles(nx, ix);
        } else if (status[nx] == 1) {
            isPartOfCycle[ix] = true;
            int i = stk.size();
            while (--i >= 0) {
                if (stk[i].first != nx)
                    isPartOfCycle[stk[i].second] = true;
                else
                    break;
            }
        } else {
            fprintf(stderr, "ERROR: dfsCycles visited vertex already out of stack.");
            exit(1);
        }
    }

    stk.pop_back();
    status[cur] = 2;
}

int uf[MAXN];
void reset() { for (int i = 0; i < MAXN; i++) uf[i] = i; }
int get(int i) { return uf[i] == i ? i : uf[i] = get(uf[i]); }
void join(int a, int b) { uf[get(b)] = get(a); }

enum Answer {UNDEFINED, LEFT, RIGHT, BOTH};
Answer ans[MAXN];

int parent[MAXN], depth[MAXN], edgeParent[MAXN];
void dfsLCA(int cur, int pre) {
    parent[cur] = pre;
    depth[cur] = depth[pre] + 1;
    status[cur] = 1;

    for (int ix : gix[cur]) {
        int nx = other(cur, ix);

        if (nx != pre) {
            // printf("%d->%d (%d)\n", cur,nx, ix);
            edgeParent[nx] = ix;
            dfsLCA(nx, cur);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0,a,b; i < m; i++) {
        scanf("%d %d", &a, &b);
        edges.push_back({a,b});
        gix[a].push_back(i);
        gix[b].push_back(i);
    }

    scanf("%d", &p);
    for (int i = 0,a,b; i < p; i++) {
        scanf("%d %d", &a, &b);
        requirements.push_back({a,b});
    }

    for (int i = 1; i <= n; i++) {
        if (status[i] == 0) {
            dfsCycles(i, -1);
        }
    }

    reset();

    for (int i = 0; i < m; i++) {
        if (isPartOfCycle[i]) {
            ans[i] = BOTH;
            join(edges[i].first, edges[i].second);
        }
    }

    for (int i = 1; i <= n; i++) {
        gix[i].clear();
        status[i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int a = get(edges[i].first), b = get(edges[i].second);
        edges[i] = {a, b};

        if (a != b) {
            gix[a].push_back(i);
            gix[b].push_back(i);

            // printf("new vertex: %d %d (%d)\n", a, b, i);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (status[i] == 0) {
            dfsLCA(i, i);
        }
    }

    for (int i = 0; i < p; i++) {
        int a = get(requirements[i].first), b = get(requirements[i].second);

        while (a != b) {
            int da = depth[a], db = depth[b];

            // printf("%d (%d) %d (%d)\n", a, edgeParent[a], b, edgeParent[b]);

            if (da >= db) {
                ans[edgeParent[a]] = isFirst(a, edgeParent[a]) ? RIGHT : LEFT;
                a = parent[a];
            }

            if (db >= da) {
                ans[edgeParent[b]] = isFirst(b, edgeParent[b]) ? LEFT : RIGHT;
                b = parent[b];
            }
        }
    }

    for (int i = 0; i < m; i++) {
        switch(ans[i]) {
            case LEFT: printf("L"); break;
            case RIGHT: printf("R"); break;
            default: printf("B");
        }
    }

    printf("\n");
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:83: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:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~
oneway.cpp:93: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 4 ms 3064 KB Output is correct
2 Correct 5 ms 3172 KB Output is correct
3 Correct 7 ms 3412 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 6 ms 3476 KB Output is correct
6 Correct 6 ms 3560 KB Output is correct
7 Correct 5 ms 3560 KB Output is correct
8 Correct 6 ms 3560 KB Output is correct
9 Correct 4 ms 3716 KB Output is correct
10 Correct 4 ms 3776 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3172 KB Output is correct
3 Correct 7 ms 3412 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 6 ms 3476 KB Output is correct
6 Correct 6 ms 3560 KB Output is correct
7 Correct 5 ms 3560 KB Output is correct
8 Correct 6 ms 3560 KB Output is correct
9 Correct 4 ms 3716 KB Output is correct
10 Correct 4 ms 3776 KB Output is correct
11 Correct 1204 ms 9320 KB Output is correct
12 Correct 1851 ms 11508 KB Output is correct
13 Correct 1917 ms 13704 KB Output is correct
14 Correct 1104 ms 15680 KB Output is correct
15 Correct 858 ms 16972 KB Output is correct
16 Correct 150 ms 16972 KB Output is correct
17 Correct 159 ms 19376 KB Output is correct
18 Correct 157 ms 19376 KB Output is correct
19 Correct 163 ms 22900 KB Output is correct
20 Correct 409 ms 22900 KB Output is correct
21 Correct 93 ms 22900 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 5 ms 3172 KB Output is correct
3 Correct 7 ms 3412 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 6 ms 3476 KB Output is correct
6 Correct 6 ms 3560 KB Output is correct
7 Correct 5 ms 3560 KB Output is correct
8 Correct 6 ms 3560 KB Output is correct
9 Correct 4 ms 3716 KB Output is correct
10 Correct 4 ms 3776 KB Output is correct
11 Correct 1204 ms 9320 KB Output is correct
12 Correct 1851 ms 11508 KB Output is correct
13 Correct 1917 ms 13704 KB Output is correct
14 Correct 1104 ms 15680 KB Output is correct
15 Correct 858 ms 16972 KB Output is correct
16 Correct 150 ms 16972 KB Output is correct
17 Correct 159 ms 19376 KB Output is correct
18 Correct 157 ms 19376 KB Output is correct
19 Correct 163 ms 22900 KB Output is correct
20 Correct 409 ms 22900 KB Output is correct
21 Correct 93 ms 22900 KB Output is correct
22 Execution timed out 3037 ms 26936 KB Time limit exceeded
23 Halted 0 ms 0 KB -