oj.uz

Submission #1010247

# Submission time Handle Problem Language Result Execution time Memory
1010247 2024-06-28T14:51:30 Z ByeWorld One-Way Streets (CEOI17_oneway) C++14
100 / 100
 184 ms 77140 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 3e5+10;
const int MAXA = 2e3+10;
const int INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int n, m, q;
int u[MAXN], v[MAXN];
vector <pii> adj[MAXN];
int tim, disc[MAXN], low[MAXN], col[MAXN];
int up[MAXN], dw[MAXN], br[MAXN];
int ty[MAXN];

void dfs(int nw, int idxpar){
    disc[nw] = low[nw] = ++tim;
    for(auto [nx, idx] : adj[nw]){
        if(idx == idxpar) continue;
        if(disc[nx] == -1){
            dfs(nx, idx); 
            if(disc[nx] == low[nx]){
                br[idx] = 1; // bridge
            }
            low[nw] = min(low[nw], low[nx]);
        } else low[nw] = min(low[nw], disc[nx]); // udh pernah vis

    }
}
void color(int nw, int COL){
    col[nw] = COL;
    for(auto [nx, idx] : adj[nw]){
        if(col[nx]!=-1 || br[idx]) continue;
        color(nx, COL);
    }
}
vector <pii> edge[MAXN];
int anc[MAXN][LOG+5], dep[MAXN];
void trav(int nw, int par){
    disc[nw] = 1;
    anc[nw][0] = par; dep[nw] = dep[par]+1;
    for(auto [nx, idx] : edge[nw]){
        if(nx==par) continue;
        trav(nx, nw);
    }
}

int LCA(int x, int y){
    if(dep[x] > dep[y]) swap(x, y);
    for(int i=LOG-1; i>=0; i--){
        if(dep[anc[y][i]] >= dep[x]){
            y = anc[y][i];
        }
    }
    if(x==y) return x;
    for(int i=LOG-1; i>=0; i--){
        if(anc[y][i] != anc[x][i]){
            y = anc[y][i]; x = anc[x][i];
        }
    }
    return anc[x][0];
}

int idxedge[MAXN];
void bd(int nw){
    // cout << nw << " nw\n";
    disc[nw] = 1;
    for(auto [nx, idx] : edge[nw]){ // nw->nx = idx
        if(disc[nx]==1) continue;
        bd(nx);
        idxedge[nx] = idx;
        up[nw] += up[nx]; dw[nw] += dw[nx];
    }
}
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        cin >> u[i] >> v[i];
        adj[u[i]].pb({v[i], i}); adj[v[i]].pb({u[i], i});
    }
    // 1. detect bridge
    memset(disc, -1, sizeof disc);
    for(int i=1; i<=n; i++){
        if(disc[i] == -1) dfs(i, 0);
    }
    // 2. bridge tree
    int cnt = 0; memset(col, -1, sizeof col);
    for(int i=1; i<=n; i++){
        if(col[i] == -1) color(i, ++cnt);
    }
    for(int i=1; i<=m; i++){
        if(col[u[i]] == col[v[i]]) continue;
        edge[col[u[i]]].pb({col[v[i]], i});
        edge[col[v[i]]].pb({col[u[i]], -i});
    }
    // for(int i=1; i<=n; i++){
    //     cout << i << ' ' << col[i] << " pp\n";
    // }
    // for(int i=1; i<=m; i++){
    //     if(br[i]) cout << u[i] << ' ' << v[i] << " bri\n";
    // }
    // LCA
    memset(disc, -1, sizeof disc);
    for(int i=1; i<=n; i++){
        if(disc[i]==-1) trav(i, 0);
    }
    // cout << "pp\n";
    for(int j=1; j<LOG; j++)
        for(int i=1; i<=n; i++)
            anc[i][j] = anc[ anc[i][j-1] ][j-1];
    
    cin >> q;
    while(q--){
        int x, y; cin >> x >> y;
        x = col[x]; y = col[y];
        int lca = LCA(x, y);
        up[x]++; up[lca]--;
        dw[y]++; dw[lca]--; 
        // cout << lca << " lca\n";
        // cout << x << ' ' << dep[x] << " up\n";
        // cout << y << ' ' << dep[y] << " dw\n";
    }
    // for(int i=1; i<=3; i++){
    //     cout << i << ' ' << up[i] << ' ' << dw[i] << "pre\n";
    // }
    memset(disc, -1, sizeof disc);
    for(int i=1; i<=cnt; i++){
        if(disc[i] == -1){
            // cout << i << " ii\n"; 
            bd(i);
        }
    }
    for(int i=1; i<=n; i++){ // node di bridge tree
        // cout << i << ' ' << idxedge[i] << " pp\n";
        if(up[i]!=0 && dw[i]!=0) continue;
        int id = idxedge[i];
        // cout << i << ' ' <<up[i] << ' ' << dw[i] << " updw\n";
        if(up[i]!=0){ // nx->nw
            if(id < 0) ty[-id] = -1;
            else ty[id] = 1;
        }

        if(dw[i]!=0){ // nw->nx
            if(id < 0) ty[-id] = 1;
            else ty[id] = -1;
        }
    }

    // OUTPUT
    for(int i=1; i<=m; i++){
        if(ty[i]==1) cout << 'L';
        else if(ty[i]==-1) cout << 'R';
        else cout << 'B';
    }
    cout << '\n';
}

Compilation message

oneway.cpp: In function 'void dfs(long long int, long long int)':
oneway.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto [nx, idx] : adj[nw]){
      |              ^
oneway.cpp: In function 'void color(long long int, long long int)':
oneway.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [nx, idx] : adj[nw]){
      |              ^
oneway.cpp: In function 'void trav(long long int, long long int)':
oneway.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [nx, idx] : edge[nw]){
      |              ^
oneway.cpp: In function 'void bd(long long int)':
oneway.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for(auto [nx, idx] : edge[nw]){ // nw->nx = idx
      |              ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37212 KB Output is correct
2 Correct 6 ms 37356 KB Output is correct
3 Correct 6 ms 37416 KB Output is correct
4 Correct 8 ms 37464 KB Output is correct
5 Correct 6 ms 37464 KB Output is correct
6 Correct 6 ms 35448 KB Output is correct
7 Correct 7 ms 37468 KB Output is correct
8 Correct 6 ms 37624 KB Output is correct
9 Correct 5 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37212 KB Output is correct
2 Correct 6 ms 37356 KB Output is correct
3 Correct 6 ms 37416 KB Output is correct
4 Correct 8 ms 37464 KB Output is correct
5 Correct 6 ms 37464 KB Output is correct
6 Correct 6 ms 35448 KB Output is correct
7 Correct 7 ms 37468 KB Output is correct
8 Correct 6 ms 37624 KB Output is correct
9 Correct 5 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct
11 Correct 58 ms 47388 KB Output is correct
12 Correct 55 ms 50260 KB Output is correct
13 Correct 65 ms 55408 KB Output is correct
14 Correct 68 ms 64588 KB Output is correct
15 Correct 82 ms 66996 KB Output is correct
16 Correct 86 ms 70480 KB Output is correct
17 Correct 92 ms 72272 KB Output is correct
18 Correct 85 ms 70484 KB Output is correct
19 Correct 84 ms 73556 KB Output is correct
20 Correct 67 ms 53480 KB Output is correct
21 Correct 70 ms 53328 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37212 KB Output is correct
2 Correct 6 ms 37356 KB Output is correct
3 Correct 6 ms 37416 KB Output is correct
4 Correct 8 ms 37464 KB Output is correct
5 Correct 6 ms 37464 KB Output is correct
6 Correct 6 ms 35448 KB Output is correct
7 Correct 7 ms 37468 KB Output is correct
8 Correct 6 ms 37624 KB Output is correct
9 Correct 5 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct
11 Correct 58 ms 47388 KB Output is correct
12 Correct 55 ms 50260 KB Output is correct
13 Correct 65 ms 55408 KB Output is correct
14 Correct 68 ms 64588 KB Output is correct
15 Correct 82 ms 66996 KB Output is correct
16 Correct 86 ms 70480 KB Output is correct
17 Correct 92 ms 72272 KB Output is correct
18 Correct 85 ms 70484 KB Output is correct
19 Correct 84 ms 73556 KB Output is correct
20 Correct 67 ms 53480 KB Output is correct
21 Correct 70 ms 53328 KB Output is correct
22 Correct 174 ms 73428 KB Output is correct
23 Correct 170 ms 71428 KB Output is correct
24 Correct 151 ms 71508 KB Output is correct
25 Correct 184 ms 77140 KB Output is correct
26 Correct 170 ms 72980 KB Output is correct
27 Correct 173 ms 71764 KB Output is correct
28 Correct 58 ms 40788 KB Output is correct
29 Correct 101 ms 54048 KB Output is correct
30 Correct 103 ms 54356 KB Output is correct
31 Correct 102 ms 54608 KB Output is correct
32 Correct 138 ms 64392 KB Output is correct