oj.uz

Submission #563748

# Submission time Handle Problem Language Result Execution time Memory
563748 2022-05-18T05:05:20 Z minhcool One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 71272 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 9 ms 14420 KB Output is correct
3 Correct 11 ms 14616 KB Output is correct
4 Correct 10 ms 14804 KB Output is correct
5 Correct 10 ms 14932 KB Output is correct
6 Correct 8 ms 14592 KB Output is correct
7 Correct 10 ms 14900 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 9 ms 14548 KB Output is correct
10 Correct 9 ms 14640 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 9 ms 14420 KB Output is correct
3 Correct 11 ms 14616 KB Output is correct
4 Correct 10 ms 14804 KB Output is correct
5 Correct 10 ms 14932 KB Output is correct
6 Correct 8 ms 14592 KB Output is correct
7 Correct 10 ms 14900 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 9 ms 14548 KB Output is correct
10 Correct 9 ms 14640 KB Output is correct
11 Correct 259 ms 31260 KB Output is correct
12 Correct 328 ms 32680 KB Output is correct
13 Correct 316 ms 35160 KB Output is correct
14 Correct 352 ms 41748 KB Output is correct
15 Correct 360 ms 44172 KB Output is correct
16 Correct 450 ms 59656 KB Output is correct
17 Correct 418 ms 62016 KB Output is correct
18 Correct 470 ms 59852 KB Output is correct
19 Correct 429 ms 63664 KB Output is correct
20 Correct 230 ms 33580 KB Output is correct
21 Correct 196 ms 32452 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 11 ms 14616 KB Output is correct
4 Correct 10 ms 14804 KB Output is correct
5 Correct 10 ms 14932 KB Output is correct
6 Correct 8 ms 14592 KB Output is correct
7 Correct 10 ms 14900 KB Output is correct
8 Correct 10 ms 14804 KB Output is correct
9 Correct 9 ms 14548 KB Output is correct
10 Correct 9 ms 14640 KB Output is correct
11 Correct 259 ms 31260 KB Output is correct
12 Correct 328 ms 32680 KB Output is correct
13 Correct 316 ms 35160 KB Output is correct
14 Correct 352 ms 41748 KB Output is correct
15 Correct 360 ms 44172 KB Output is correct
16 Correct 450 ms 59656 KB Output is correct
17 Correct 418 ms 62016 KB Output is correct
18 Correct 470 ms 59852 KB Output is correct
19 Correct 429 ms 63664 KB Output is correct
20 Correct 230 ms 33580 KB Output is correct
21 Correct 196 ms 32452 KB Output is correct
22 Correct 895 ms 65860 KB Output is correct
23 Correct 557 ms 63376 KB Output is correct
24 Correct 545 ms 63372 KB Output is correct
25 Execution timed out 3063 ms 71272 KB Time limit exceeded
26 Halted 0 ms 0 KB -