oj.uz

Submission #563738

# Submission time Handle Problem Language Result Execution time Memory
563738 2022-05-18T04:56:33 Z minhcool One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 115324 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#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 = 3e5 + 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];
multiset<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();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42572 KB Output is correct
2 Correct 22 ms 42580 KB Output is correct
3 Correct 23 ms 42836 KB Output is correct
4 Correct 24 ms 43236 KB Output is correct
5 Correct 23 ms 43220 KB Output is correct
6 Correct 23 ms 42736 KB Output is correct
7 Correct 26 ms 43248 KB Output is correct
8 Correct 26 ms 43252 KB Output is correct
9 Correct 23 ms 42836 KB Output is correct
10 Correct 24 ms 42800 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42572 KB Output is correct
2 Correct 22 ms 42580 KB Output is correct
3 Correct 23 ms 42836 KB Output is correct
4 Correct 24 ms 43236 KB Output is correct
5 Correct 23 ms 43220 KB Output is correct
6 Correct 23 ms 42736 KB Output is correct
7 Correct 26 ms 43248 KB Output is correct
8 Correct 26 ms 43252 KB Output is correct
9 Correct 23 ms 42836 KB Output is correct
10 Correct 24 ms 42800 KB Output is correct
11 Correct 278 ms 63056 KB Output is correct
12 Correct 295 ms 64596 KB Output is correct
13 Correct 305 ms 67748 KB Output is correct
14 Correct 364 ms 76592 KB Output is correct
15 Correct 368 ms 80304 KB Output is correct
16 Correct 482 ms 102728 KB Output is correct
17 Correct 505 ms 106000 KB Output is correct
18 Correct 491 ms 103364 KB Output is correct
19 Correct 468 ms 107776 KB Output is correct
20 Correct 245 ms 65304 KB Output is correct
21 Correct 221 ms 64420 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42572 KB Output is correct
2 Correct 22 ms 42580 KB Output is correct
3 Correct 23 ms 42836 KB Output is correct
4 Correct 24 ms 43236 KB Output is correct
5 Correct 23 ms 43220 KB Output is correct
6 Correct 23 ms 42736 KB Output is correct
7 Correct 26 ms 43248 KB Output is correct
8 Correct 26 ms 43252 KB Output is correct
9 Correct 23 ms 42836 KB Output is correct
10 Correct 24 ms 42800 KB Output is correct
11 Correct 278 ms 63056 KB Output is correct
12 Correct 295 ms 64596 KB Output is correct
13 Correct 305 ms 67748 KB Output is correct
14 Correct 364 ms 76592 KB Output is correct
15 Correct 368 ms 80304 KB Output is correct
16 Correct 482 ms 102728 KB Output is correct
17 Correct 505 ms 106000 KB Output is correct
18 Correct 491 ms 103364 KB Output is correct
19 Correct 468 ms 107776 KB Output is correct
20 Correct 245 ms 65304 KB Output is correct
21 Correct 221 ms 64420 KB Output is correct
22 Execution timed out 3085 ms 115324 KB Time limit exceeded
23 Halted 0 ms 0 KB -