oj.uz

Submission #563750

# Submission time Handle Problem Language Result Execution time Memory
563750 2022-05-18T05:06:37 Z minhcool One-Way Streets (CEOI17_oneway) C++17
100 / 100
 615 ms 71328 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, p;

vector<int> Adj[N], Adj2[N];
vector<ii> Adj3[N];

vector<ii> edges;

struct cmp{
    bool operator()(const ii& a, const ii& b)const{
        return a.fi > b.fi;
    }
};

set<ii> bridges;

int cnt;
int ti[N], low[N];

char ans[N];


map<ii, vector<int>> mp;
map<ii, vector<int>> mp2;

void dfs(int u, int p){
    cnt++;
    ti[u] = low[u] = cnt;
    for(auto v : Adj[u]){
        if(ti[v]){
            if(mp[{min(u, v), max(u, v)}].size() > 1) low[u] = min(low[u], ti[v]);
            if(v != p) low[u] = min(low[u], ti[v]);
        }
        else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(ti[u] < low[v]){
                    //cout << u << " " << v << "\n";
                bridges.insert({min(u, v), max(u, v)});
            }
        }
    }
}

int cnt_comp;
int comp[N];

void dfs2(int u){
    //cout << u << "\n";
    comp[u] = cnt_comp;
    for(auto v : Adj2[u]){
        if(comp[v]) continue;
        dfs2(v);
    }
}

int sz[N], rt[N], answ[N];

vector<ii> que[N];
set<ii, cmp> ques[N];// for component

int sparse[N][20], d[N];
int ind[N];

void dfs3(int u, int p){
    //cout << "EDGE " << u << " " << ind[u] << "\n";
    for(auto it : Adj3[u]){
        int v = it.fi;
        if(v == p) continue;
        d[v] = d[u] + 1;
        sparse[v][0] = u;
        for(int i = 1; i <= 19; i++) sparse[v][i] = sparse[sparse[v][i - 1]][i - 1];
        //cout << v << "\n";
        //for(int i = 0; i <= 19; i++) cout << sparse[v][i] << " ";
        //cout << "\n";
        ind[v] = it.se + 1;
        dfs3(v, u);
    }
}

int lca(int x, int y){
    if(d[x] > d[y]) swap(x, y);
    //cout << x << " " << y << " " << d[x] << " " << d[y] << "\n";
    for(int i = 19; i >= 0; i--){
        if(d[y] >= (d[x] + (1LL << i))){
            //cout << i << "\n";
            y = sparse[y][i];
        }
    }
    assert(d[x] == d[y]);
    //cout << x << " " << y << "\n";
    if(x == y) return x;
    for(int i = 19; i >= 0; i--){
        if(sparse[x][i] != sparse[y][i]){
            x = sparse[x][i];
            y = sparse[y][i];
        }
    }
    return sparse[x][0];
}

int root(int x){
    return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

void merge(int x, int y){
    x = root(x), y = root(y);
    if(x == y) return;
    if(sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y], rt[y] = x;
    //cout << ques[x].size() << " " << ques[y].size() << "\n";
    for(auto it : ques[y]) ques[x].insert(it);
    ques[y].clear();
}

void dfs4(int u, int p){
    for(auto it : Adj3[u]){
        int v = it.fi;
        if(v == p) continue;
        dfs4(v, u);
        merge(u, v);
    }
    //return;
    int temp = root(u);
    for(auto it : que[u]) ques[temp].insert(it);
    //if(u == 137) cout << ques[temp].size() << "\n";
    while(ques[temp].size() && (*ques[temp].begin()).fi >= d[u]) ques[temp].erase(ques[temp].begin());
    //for(auto it : ques[temp]) assert(it.fi < d[u]);
    if(!ind[u]) return;
    if(ques[temp].size()){
        //cout << u << " " << p << " " << ind[u] << " " << temp << " " << ques[temp].size() << "\n";
        //cout << (*ques[temp].begin()).fi << " " << d[u] << "\n";
        bool x = (*ques[temp].begin()).se;
        answ[ind[u] - 1] = (!x ? u : p);
    }
    else{
        //if(ind[u] == 95) cout << u << "\n";
        //assert(ind[u] - 1 != 94);
        ans[ind[u] - 1] = 'B';
       // cout << ind[u] << "\n";
    }
}

void process(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        edges.pb({x, y});
        mp[{min(x, y), max(x, y)}].pb(i);
        //Adj[x].pb(y);
        //Adj[y].pb(x);
    }
    for(auto it : mp){
        Adj[it.fi.fi].pb(it.fi.se);
        Adj[it.fi.se].pb(it.fi.fi);
        if(it.se.size() >= 2){
            //Adj[it.fi.fi].pb(it.fi.se);
            //Adj[it.fi.se].pb(it.fi.fi);
        }
    }
    for(int i = 1; i <= n; i++) if(!ti[i]) dfs(i, i);
    //for(auto it : bridges) cout << it.fi << " " << it.se << "\n";

    for(int i = 0; i < m; i++){
        if(mp[{min(edges[i].fi, edges[i].se), max(edges[i].fi, edges[i].se)}].size() > 1){
                //cout<<"OK\n";
       // cout << i << " " << mp[{min(edges[i].fi, edges[i].se), max(edges[i].fi, edges[i].se)}][0] << "\n";
            ans[i] = 'B';
            if(i == mp[{min(edges[i].fi, edges[i].se), max(edges[i].fi, edges[i].se)}][0]){
                    //cout << "OK\n";
                Adj2[edges[i].fi].pb(edges[i].se);
                Adj2[edges[i].se].pb(edges[i].fi);
            }
            continue;
        }
        if(bridges.find({min(edges[i].fi, edges[i].se), max(edges[i].fi, edges[i].se)}) == bridges.end()){
            ans[i] = 'B';
            Adj2[edges[i].fi].pb(edges[i].se);
            Adj2[edges[i].se].pb(edges[i].fi);
           // cout << edges[i].fi << " " << edges[i].se << "\n";
            continue;
        }
        //cout << i << "\n";
    }
    for(int i = 1; i <= n; i++){
        if(!comp[i]){
            cnt_comp++;
            dfs2(i);
        }
    }
    //for(int i = 1; i <= n; i++) cout << i << " " << low[i] << " " << ti[i] << " " << comp[i] << "\n";
   // return;
    for(int i = 0; i < m; i++){
        if(ans[i] != 'B'){
            assert(comp[edges[i].fi] != comp[edges[i].se]);
            //cout << edges[i].fi << " " << edges[i].se << "\n";
            //cout << comp[edges[i].fi] << " " << comp[edges[i].se] << "\n";
           // Adj3[comp[edges[i].fi]].pb({comp[edges[i].se], i});
        //    Adj3[comp[edges[i].se]].pb({comp[edges[i].fi], i});
            mp2[{min(comp[edges[i].fi], comp[edges[i].se]), max(comp[edges[i].fi], comp[edges[i].se])}].pb(i);
        }
    }
    for(auto it : mp2){
        if(it.se.size() > 1){
            for(auto temp : mp2[it.fi]){
                ans[temp] = 'B';
            }
        }
        int x = mp2[it.fi][0];
        Adj3[it.fi.fi].pb({it.fi.se, x});
        Adj3[it.fi.se].pb({it.fi.fi, x});
        //cout << it.fi.fi << " " << it.fi.se << " " << x << "\n";
    }
    //return;
    for(int i = 1; i <= cnt_comp; i++) if(!d[i]) dfs3(i, i);
    //cout << "OK\n";
    cin >> p;
    for(int i = 1; i <= p; i++){
        int x, y;
        cin >> x >> y;
        if(comp[x] == comp[y]) continue;
        int z = lca(comp[x], comp[y]);
        //cout << comp[x] << " " << comp[y] << " " << z << "\n";
        que[comp[x]].pb({d[z], 0});
        que[comp[y]].pb({d[z], 1});
    }
    for(int i = 1; i <= cnt_comp; i++){
        sz[i] = 1, rt[i] = i;
    }
    for(int i = 1; i <= cnt_comp; i++){
        if(!d[i]){
          //  cout << i << "\n";
            dfs4(i, i);
        }
    }
    for(int i = 0; i < m; i++){
        if(ans[i] != 'B'){
            if(answ[i] == comp[edges[i].fi]) ans[i] = 'R';
            else ans[i] = 'L';
        }
        //cout << i << " " << edges[i].fi << " " << edges[i].se << "\n";
        cout << ans[i] << "";
    }
    string s;
    cin >> s;
    for(int i = 0; i < m; i++){
        /*
        if(i != 771){
            //ii temp1 = {329, 139}, temp2 = {137, 329};
            //assert(edges[i] != temp1);
            //assert(edges[i] != temp2);
        }*/
        //if(ans[i] != s[i]) cout << i << " " << s[i] << " " << ans[i] << "\n";
    }
}

signed main(){
  //  freopen("temp.inp", "r", stdin);
    //freopen("temp.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    process();
}

Compilation message

oneway.cpp:13:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   13 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14676 KB Output is correct
4 Correct 9 ms 14804 KB Output is correct
5 Correct 9 ms 14868 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 10 ms 14932 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 9 ms 14616 KB Output is correct
10 Correct 10 ms 14620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14676 KB Output is correct
4 Correct 9 ms 14804 KB Output is correct
5 Correct 9 ms 14868 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 10 ms 14932 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 9 ms 14616 KB Output is correct
10 Correct 10 ms 14620 KB Output is correct
11 Correct 220 ms 31272 KB Output is correct
12 Correct 235 ms 32780 KB Output is correct
13 Correct 274 ms 35096 KB Output is correct
14 Correct 322 ms 41748 KB Output is correct
15 Correct 338 ms 44120 KB Output is correct
16 Correct 433 ms 59576 KB Output is correct
17 Correct 413 ms 62044 KB Output is correct
18 Correct 448 ms 59888 KB Output is correct
19 Correct 402 ms 63588 KB Output is correct
20 Correct 220 ms 33600 KB Output is correct
21 Correct 197 ms 32472 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14676 KB Output is correct
4 Correct 9 ms 14804 KB Output is correct
5 Correct 9 ms 14868 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 10 ms 14932 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 9 ms 14616 KB Output is correct
10 Correct 10 ms 14620 KB Output is correct
11 Correct 220 ms 31272 KB Output is correct
12 Correct 235 ms 32780 KB Output is correct
13 Correct 274 ms 35096 KB Output is correct
14 Correct 322 ms 41748 KB Output is correct
15 Correct 338 ms 44120 KB Output is correct
16 Correct 433 ms 59576 KB Output is correct
17 Correct 413 ms 62044 KB Output is correct
18 Correct 448 ms 59888 KB Output is correct
19 Correct 402 ms 63588 KB Output is correct
20 Correct 220 ms 33600 KB Output is correct
21 Correct 197 ms 32472 KB Output is correct
22 Correct 615 ms 65920 KB Output is correct
23 Correct 547 ms 63336 KB Output is correct
24 Correct 550 ms 63460 KB Output is correct
25 Correct 556 ms 71328 KB Output is correct
26 Correct 538 ms 66748 KB Output is correct
27 Correct 530 ms 63984 KB Output is correct
28 Correct 73 ms 16816 KB Output is correct
29 Correct 241 ms 34816 KB Output is correct
30 Correct 245 ms 34876 KB Output is correct
31 Correct 246 ms 34388 KB Output is correct
32 Correct 296 ms 44316 KB Output is correct