oj.uz

Submission #775959

# Submission time Handle Problem Language Result Execution time Memory
775959 2023-07-07T07:46:11 Z egekabas One-Way Streets (CEOI17_oneway) C++14
100 / 100
 252 ms 38856 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define MAXN 100009
#define LOGN 21
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;


int n, m;
vector<pii> originalGraph[MAXN];
int edgeFirst[MAXN];

int noReach;
vector<int> reachFrom[MAXN], reachTo[MAXN];

bool bridgeVisited[MAXN], isBridge[MAXN];
int tin[MAXN], low[MAXN];
int curTime = 0;
void findBridges(int v, int p){
    bridgeVisited[v] = true;
    tin[v] = low[v] = ++curTime;

    for(auto edge : originalGraph[v]){
        int u = edge.ff;
        int edgeIdx = edge.ss;
        if(u == p){
            continue;
        } else if(bridgeVisited[u]){
            low[v] = min(low[v], tin[u]);
        } else{
            findBridges(u, v);
            low[v] = min(low[v], low[u]);
            if(low[u] > low[v]){
                isBridge[edgeIdx] = true;
            }
        }
    }
}

int nodeGroup[MAXN];
vector<pii> groupCon[MAXN];
int curGroup = 0;
void findGroup(int v){
    nodeGroup[v] = curGroup;
    for(auto edge : originalGraph[v]){
        int u = edge.ff;
        int edgeIdx = edge.ss;
        
        if(isBridge[edgeIdx]){
            if(nodeGroup[u] && nodeGroup[u] != nodeGroup[v]){
                groupCon[nodeGroup[v]].pb({nodeGroup[u], edgeIdx});
                groupCon[nodeGroup[u]].pb({nodeGroup[v], edgeIdx});
            }
        } else{
            if(!nodeGroup[u]){
                findGroup(u);
            }
        }
    }
}

bool finalVisited[MAXN];
int depth[MAXN];
int prt[MAXN][LOGN];
void createLCA(int v, int p){
    finalVisited[v] = true;
    depth[v] = depth[p]+1;
    prt[v][0] = p;
    for(int i = 1; i < LOGN; ++i){
        prt[v][i] = prt[prt[v][i-1]][i-1];
    }

    for(auto edge : groupCon[v]){
        int u = edge.ff;
        if(u != p){
            createLCA(u, v);
        }
    }
}

int lca(int x, int y){
    if(depth[y] > depth[x]){
        swap(x, y);
    }
    for(int i = LOGN-1; i >= 0; --i){
        if(depth[prt[x][i]] >= depth[y]){
            x = prt[x][i];
        }
    }
    if(x == y){
        return x;
    }
    for(int i = LOGN-1; i >= 0; --i){
        if(prt[x][i] != prt[y][i]){
            x = prt[x][i];
            y = prt[y][i];
        }
    }
    return prt[x][0];
}

char ans[MAXN];

int fromMin[MAXN];
int toMin[MAXN];

void calcAns(int v, int p){
    fromMin[v] = toMin[v] = INF;

    for(auto u : reachFrom[v]){
        fromMin[v] = min(fromMin[v], depth[lca(v, u)]);
    }
    for(auto u : reachTo[v]){
        toMin[v] = min(toMin[v], depth[lca(v, u)]);
    }
    
    for(auto edge : groupCon[v]){
        int u = edge.ff;
        int edgeIdx = edge.ss;
        if(u != p){
            calcAns(u, v);
            fromMin[v] = min(fromMin[v], fromMin[u]);
            toMin[v] = min(toMin[v], toMin[u]);
            
            if(fromMin[u] < depth[u]){
                ans[edgeIdx] = nodeGroup[edgeFirst[edgeIdx]] == u ? 'R' : 'L';
            } else if(toMin[u] < depth[u]){
                ans[edgeIdx] = nodeGroup[edgeFirst[edgeIdx]] == u ? 'L' : 'R';
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        originalGraph[x].pb({y, i});
        originalGraph[y].pb({x, i});
        edgeFirst[i] = x;
        ans[i] = 'B';
    }

    for(int i = 1; i <= n; ++i){
        if(!bridgeVisited[i]){
            findBridges(i, 0);
        }
    }

    for(int i = 1; i <= n; ++i){
        if(!nodeGroup[i]){
            ++curGroup;
            findGroup(i);
        }
    }

    cin >> noReach;
    for(int i = 0; i < noReach; ++i){
        int x, y;
        cin >> x >> y;
        reachFrom[nodeGroup[x]].pb(nodeGroup[y]);
        reachTo[nodeGroup[y]].pb(nodeGroup[x]);
    }


    for(int i = 1; i <= curGroup; ++i){
        if(!finalVisited[i]){
            createLCA(i, 0);
            calcAns(i, 0);
        }
    }

    for(int i = 0; i < m; ++i){
        cout << ans[i];
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 5 ms 9744 KB Output is correct
10 Correct 6 ms 9736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 5 ms 9744 KB Output is correct
10 Correct 6 ms 9736 KB Output is correct
11 Correct 30 ms 15664 KB Output is correct
12 Correct 37 ms 16620 KB Output is correct
13 Correct 39 ms 18124 KB Output is correct
14 Correct 60 ms 21516 KB Output is correct
15 Correct 52 ms 22984 KB Output is correct
16 Correct 82 ms 29692 KB Output is correct
17 Correct 101 ms 31420 KB Output is correct
18 Correct 80 ms 29768 KB Output is correct
19 Correct 92 ms 32724 KB Output is correct
20 Correct 34 ms 16152 KB Output is correct
21 Correct 33 ms 16020 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 5 ms 9744 KB Output is correct
10 Correct 6 ms 9736 KB Output is correct
11 Correct 30 ms 15664 KB Output is correct
12 Correct 37 ms 16620 KB Output is correct
13 Correct 39 ms 18124 KB Output is correct
14 Correct 60 ms 21516 KB Output is correct
15 Correct 52 ms 22984 KB Output is correct
16 Correct 82 ms 29692 KB Output is correct
17 Correct 101 ms 31420 KB Output is correct
18 Correct 80 ms 29768 KB Output is correct
19 Correct 92 ms 32724 KB Output is correct
20 Correct 34 ms 16152 KB Output is correct
21 Correct 33 ms 16020 KB Output is correct
22 Correct 252 ms 35300 KB Output is correct
23 Correct 207 ms 33440 KB Output is correct
24 Correct 189 ms 33636 KB Output is correct
25 Correct 241 ms 38856 KB Output is correct
26 Correct 217 ms 34840 KB Output is correct
27 Correct 194 ms 33476 KB Output is correct
28 Correct 47 ms 14524 KB Output is correct
29 Correct 76 ms 18084 KB Output is correct
30 Correct 73 ms 18116 KB Output is correct
31 Correct 67 ms 18368 KB Output is correct
32 Correct 124 ms 25016 KB Output is correct