oj.uz

Submission #98002

# Submission time Handle Problem Language Result Execution time Memory
98002 2019-02-19T17:43:41 Z popovicirobert One-Way Streets (CEOI17_oneway) C++14
100 / 100
 207 ms 22848 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;

vector < pair <int, int> > g[MAXN + 1];
int lvl[MAXN + 1], low[MAXN + 1];
int id[MAXN + 1], cnt;
stack <int> stk;

char sol[MAXN + 1];

void dfs(int nod, int par) {
    lvl[nod] = lvl[par] + 1;
    low[nod] = lvl[nod];
    stk.push(nod);
    bool ok = 0;
    for(auto it : g[nod]) {
        if(lvl[it.first] == 0) {
            dfs(it.first, nod);
            low[nod] = min(low[nod], low[it.first]);
            if(low[it.first] > lvl[nod]) {
                cnt++;
                while(stk.size() && stk.top() != it.first) {
                    id[stk.top()] = cnt;
                    stk.pop();
                }
                id[stk.top()] = cnt;
                stk.pop();
                sol[it.second] = 0;
            }
        }
        else {
            if(it.first != par) {
                low[nod] = min(low[nod], lvl[it.first]);
            }
            else {
                if(ok == 1) {
                    low[nod] = min(low[nod], lvl[it.first]);
                }
                ok = 1;
            }
        }
    }
}

vector < pair <int, int> > tree[MAXN + 1];
pair <int, int> edges[MAXN + 1];
bool vis[MAXN + 1];
int sp[MAXN + 1];

void dfs1(int nod, int par) {
    vis[nod] = 1;
    for(auto it : tree[nod]) {
        if(vis[it.first] == 0) {
            dfs1(it.first, nod);
            sp[nod] += sp[it.first];
            if(sp[it.first] > 0) {
                if(id[edges[it.second].first] == it.first) {
                    sol[it.second] = 'R';
                }
                else {
                    sol[it.second] = 'L';
                }
            }
            else if(sp[it.first] < 0) {
                if(id[edges[it.second].first] == it.first) {
                    sol[it.second] = 'L';
                }
                else {
                    sol[it.second] = 'R';
                }
            }
            else {
                sol[it.second] = 'B';
            }
        }
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        edges[i] = {x, y};
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    memset(sol, 'B', sizeof(sol));
    for(i = 1; i <= n; i++) {
        if(lvl[i] == 0) {
            dfs(i, 0);
        }
    }
    cnt++;
    while(stk.size()) {
        id[stk.top()] = cnt;
        stk.pop();
    }
    for(i = 1; i <= n; i++) {
        for(auto it : g[i]) {
            if(id[i] != id[it.first]) {
                tree[id[i]].push_back({id[it.first], it.second});
            }
        }
    }
    cin >> q;
    for(i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        sp[id[x]]++;
        sp[id[y]]--;
    }
    for(i = 1; i <= cnt; i++) {
        if(vis[i] == 0) {
            dfs1(i, 0);
        }
    }
    for(i = 1; i <= m; i++) {
        cout << sol[i];
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5248 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 7 ms 5220 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 6 ms 5248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5248 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 7 ms 5220 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 6 ms 5248 KB Output is correct
11 Correct 66 ms 11640 KB Output is correct
12 Correct 98 ms 12692 KB Output is correct
13 Correct 83 ms 13960 KB Output is correct
14 Correct 105 ms 15096 KB Output is correct
15 Correct 109 ms 15476 KB Output is correct
16 Correct 161 ms 16356 KB Output is correct
17 Correct 171 ms 18012 KB Output is correct
18 Correct 147 ms 16376 KB Output is correct
19 Correct 171 ms 19436 KB Output is correct
20 Correct 95 ms 12352 KB Output is correct
21 Correct 70 ms 11924 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 7 ms 5248 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 7 ms 5220 KB Output is correct
9 Correct 7 ms 5248 KB Output is correct
10 Correct 6 ms 5248 KB Output is correct
11 Correct 66 ms 11640 KB Output is correct
12 Correct 98 ms 12692 KB Output is correct
13 Correct 83 ms 13960 KB Output is correct
14 Correct 105 ms 15096 KB Output is correct
15 Correct 109 ms 15476 KB Output is correct
16 Correct 161 ms 16356 KB Output is correct
17 Correct 171 ms 18012 KB Output is correct
18 Correct 147 ms 16376 KB Output is correct
19 Correct 171 ms 19436 KB Output is correct
20 Correct 95 ms 12352 KB Output is correct
21 Correct 70 ms 11924 KB Output is correct
22 Correct 141 ms 19136 KB Output is correct
23 Correct 151 ms 17244 KB Output is correct
24 Correct 207 ms 17484 KB Output is correct
25 Correct 192 ms 22848 KB Output is correct
26 Correct 151 ms 18752 KB Output is correct
27 Correct 160 ms 17512 KB Output is correct
28 Correct 53 ms 9208 KB Output is correct
29 Correct 115 ms 12836 KB Output is correct
30 Correct 85 ms 13024 KB Output is correct
31 Correct 124 ms 13532 KB Output is correct
32 Correct 105 ms 16632 KB Output is correct