oj.uz

Submission #570937

# Submission time Handle Problem Language Result Execution time Memory
570937 2022-05-31T14:52:32 Z bojackduy One-Way Streets (CEOI17_oneway) C++14
100 / 100
 370 ms 48204 KB 
#include<bits/stdc++.h>
#define int long long
#define task "task"
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define allr(x, sz) (x) + 1, (x) + 1 + sz
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define MASK(x) (1LL<<(x))
#define BIT(x,i) (((x)>>(i))&1)
#define numbit(x) __builtin_popcountll(x)
 
using namespace std;
 
const int N = 1e5 + 1;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;
 
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
 
template<class t>
bool mini(t &x,t y) {
    if (x > y) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}
void file() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen(task".in", "r", stdin);
    // freopen(task".out", "w", stdout);
return ;
}
 
int n, m, p;
pii e[N];
vii a[N];
vi adj[N];
map<pii, int> mp, mp1;
 
stack<int> st;
int num[N], low[N];
 
void dfs(int u, int chu) {
    st.push(u);
    num[u] = low[u] = ++num[0];
    for (auto v: a[u]) if (v.fi != chu) {
        if (num[v.se]) mini(low[u], num[v.se]); else {
            dfs(v.se, v.fi);
            mini(low[u], low[v.se]);
        }
    }
 
    if (num[u] == low[u]) {
        int v;
        low[0]++;
        do {
            v = st.top(), st.pop();
            num[v] = low[v] = mod + low[0];
        } while (v != u);
    }
}
 
 
int cha[N];
void dfs1(int u, int chu) {
    cha[u] = chu;
    num[u] = 1;
    for (auto v: adj[u]) if (!num[v] && v != chu) {
        dfs1(v, u);
    }
}
 
 
int dp[N];
void dfs2(int u, int chu) {
    num[u] = 0;
    for (auto v: adj[u]) if (num[v] && v != chu) {
        dfs2(v, u);
        dp[u] += dp[v];
    }
}
 
void solve(int test = -1) {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[x].pb(pii(i, y));
        a[y].pb(pii(i, x));
        e[i] = pii(x, y);
    }
 
    for (int i = 1; i <= n; i++) if (!num[i])
        dfs(i, 0);
    for (int i = 1; i <= n; i++) {
        num[i] = 0;
        for (auto v: a[i]) {
            if (low[i] != low[v.se]) {
                adj[low[i] - mod].pb(low[v.se] - mod);
            }
        }
    }
    for (int i = 1; i <= low[0]; i++) if (!num[i])
        dfs1(i, 0);
    
    cin >> p;
    for (int i = 1; i <= p; i++) {
        int x, y;
        cin >> x >> y;
        x = low[x] - mod;
        y = low[y] - mod;
        dp[x]++;
        dp[y]--;
    }

    for (int i = 1; i <= low[0]; i++) if (num[i])
        dfs2(i, 0);


    for (int i = 2; i <= low[0]; i++) {
        int u = cha[i];
        mp[pii(i, u)] = dp[i];
        mp[pii(u, i)] = -dp[i];
    }
 
    for (int i = 1; i <= n; i++) {
        for (auto v: a[i]) {
            mp1[pii(i, v.se)] = mp[pii(low[i] - mod, low[v.se] - mod)];
        }
    }
 
    for (int i = 1; i <= m; i++) {
        int u = e[i].fi;
        int v = e[i].se;
        if (mp1[pii(u, v)] == 0) cout << "B"; else {
            if (mp1[pii(u, v)] > 0) cout << "R"; else cout << "L";
        } 
    }
}
 
int32_t main()  {
    file();
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5436 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5436 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 162 ms 25376 KB Output is correct
12 Correct 162 ms 26324 KB Output is correct
13 Correct 156 ms 27996 KB Output is correct
14 Correct 227 ms 32508 KB Output is correct
15 Correct 252 ms 34464 KB Output is correct
16 Correct 271 ms 43780 KB Output is correct
17 Correct 327 ms 45184 KB Output is correct
18 Correct 290 ms 43732 KB Output is correct
19 Correct 299 ms 46304 KB Output is correct
20 Correct 144 ms 25976 KB Output is correct
21 Correct 128 ms 25384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 5 ms 5460 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5436 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 162 ms 25376 KB Output is correct
12 Correct 162 ms 26324 KB Output is correct
13 Correct 156 ms 27996 KB Output is correct
14 Correct 227 ms 32508 KB Output is correct
15 Correct 252 ms 34464 KB Output is correct
16 Correct 271 ms 43780 KB Output is correct
17 Correct 327 ms 45184 KB Output is correct
18 Correct 290 ms 43732 KB Output is correct
19 Correct 299 ms 46304 KB Output is correct
20 Correct 144 ms 25976 KB Output is correct
21 Correct 128 ms 25384 KB Output is correct
22 Correct 317 ms 45116 KB Output is correct
23 Correct 298 ms 43684 KB Output is correct
24 Correct 353 ms 43644 KB Output is correct
25 Correct 370 ms 48204 KB Output is correct
26 Correct 324 ms 44824 KB Output is correct
27 Correct 315 ms 43764 KB Output is correct
28 Correct 56 ms 10784 KB Output is correct
29 Correct 175 ms 25640 KB Output is correct
30 Correct 162 ms 25724 KB Output is correct
31 Correct 175 ms 26120 KB Output is correct
32 Correct 188 ms 30864 KB Output is correct