답안 #56067 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56067	2018-07-09T18:21:28 Z	gabrielsimoes	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	1996 ms	33732 KB

oneway

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

const int MAXN = 1e5+10, MAXL = 18;

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;
                join(parent[a], a);
                a = get(parent[a]);
            }

            if (db >= da) {
                ans[edgeParent[b]] = isFirst(b, edgeParent[b]) ? LEFT : RIGHT;
                join(parent[b], b);
                b = get(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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	4 ms	3204 KB	Output is correct
3	Correct	5 ms	3240 KB	Output is correct
4	Correct	5 ms	3316 KB	Output is correct
5	Correct	4 ms	3360 KB	Output is correct
6	Correct	4 ms	3360 KB	Output is correct
7	Correct	6 ms	3368 KB	Output is correct
8	Correct	5 ms	3368 KB	Output is correct
9	Correct	5 ms	3368 KB	Output is correct
10	Correct	4 ms	3496 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	4 ms	3204 KB	Output is correct
3	Correct	5 ms	3240 KB	Output is correct
4	Correct	5 ms	3316 KB	Output is correct
5	Correct	4 ms	3360 KB	Output is correct
6	Correct	4 ms	3360 KB	Output is correct
7	Correct	6 ms	3368 KB	Output is correct
8	Correct	5 ms	3368 KB	Output is correct
9	Correct	5 ms	3368 KB	Output is correct
10	Correct	4 ms	3496 KB	Output is correct
11	Correct	1350 ms	7996 KB	Output is correct
12	Correct	1996 ms	9096 KB	Output is correct
13	Correct	1908 ms	10176 KB	Output is correct
14	Correct	1173 ms	11128 KB	Output is correct
15	Correct	824 ms	11268 KB	Output is correct
16	Correct	87 ms	11268 KB	Output is correct
17	Correct	97 ms	11284 KB	Output is correct
18	Correct	144 ms	11284 KB	Output is correct
19	Correct	149 ms	12564 KB	Output is correct
20	Correct	490 ms	12564 KB	Output is correct
21	Correct	115 ms	12564 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	4 ms	3204 KB	Output is correct
3	Correct	5 ms	3240 KB	Output is correct
4	Correct	5 ms	3316 KB	Output is correct
5	Correct	4 ms	3360 KB	Output is correct
6	Correct	4 ms	3360 KB	Output is correct
7	Correct	6 ms	3368 KB	Output is correct
8	Correct	5 ms	3368 KB	Output is correct
9	Correct	5 ms	3368 KB	Output is correct
10	Correct	4 ms	3496 KB	Output is correct
11	Correct	1350 ms	7996 KB	Output is correct
12	Correct	1996 ms	9096 KB	Output is correct
13	Correct	1908 ms	10176 KB	Output is correct
14	Correct	1173 ms	11128 KB	Output is correct
15	Correct	824 ms	11268 KB	Output is correct
16	Correct	87 ms	11268 KB	Output is correct
17	Correct	97 ms	11284 KB	Output is correct
18	Correct	144 ms	11284 KB	Output is correct
19	Correct	149 ms	12564 KB	Output is correct
20	Correct	490 ms	12564 KB	Output is correct
21	Correct	115 ms	12564 KB	Output is correct
22	Correct	200 ms	12564 KB	Output is correct
23	Correct	175 ms	12820 KB	Output is correct
24	Correct	182 ms	15164 KB	Output is correct
25	Correct	175 ms	21944 KB	Output is correct
26	Correct	170 ms	21944 KB	Output is correct
27	Correct	171 ms	22060 KB	Output is correct
28	Correct	74 ms	22060 KB	Output is correct
29	Correct	222 ms	24116 KB	Output is correct
30	Correct	108 ms	26560 KB	Output is correct
31	Correct	684 ms	29172 KB	Output is correct
32	Correct	136 ms	33732 KB	Output is correct

답안 #56067

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 30.0 / 30.0

Subtask #3 40.0 / 40.0

Subtask #1
30.0 / 30.0

Subtask #2
30.0 / 30.0

Subtask #3
40.0 / 40.0