oj.uz

Submission #563747

# Submission time Handle Problem Language Result Execution time Memory
563747 2022-05-18T05:04:03 Z minhcool One-Way Streets (CEOI17_oneway) C++17
60 / 100
 598 ms 107752 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;
     if(n > 100 && p > 100)return;
    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 42580 KB Output is correct
2 Correct 22 ms 42556 KB Output is correct
3 Correct 25 ms 42836 KB Output is correct
4 Correct 25 ms 43196 KB Output is correct
5 Correct 25 ms 43220 KB Output is correct
6 Correct 23 ms 42776 KB Output is correct
7 Correct 25 ms 43252 KB Output is correct
8 Correct 24 ms 43192 KB Output is correct
9 Correct 23 ms 42772 KB Output is correct
10 Correct 28 ms 42828 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42580 KB Output is correct
2 Correct 22 ms 42556 KB Output is correct
3 Correct 25 ms 42836 KB Output is correct
4 Correct 25 ms 43196 KB Output is correct
5 Correct 25 ms 43220 KB Output is correct
6 Correct 23 ms 42776 KB Output is correct
7 Correct 25 ms 43252 KB Output is correct
8 Correct 24 ms 43192 KB Output is correct
9 Correct 23 ms 42772 KB Output is correct
10 Correct 28 ms 42828 KB Output is correct
11 Correct 315 ms 63020 KB Output is correct
12 Correct 296 ms 64652 KB Output is correct
13 Correct 319 ms 67692 KB Output is correct
14 Correct 380 ms 76600 KB Output is correct
15 Correct 395 ms 80300 KB Output is correct
16 Correct 598 ms 102736 KB Output is correct
17 Correct 512 ms 106044 KB Output is correct
18 Correct 513 ms 103176 KB Output is correct
19 Correct 517 ms 107752 KB Output is correct
20 Correct 283 ms 65316 KB Output is correct
21 Correct 230 ms 64324 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42580 KB Output is correct
2 Correct 22 ms 42556 KB Output is correct
3 Correct 25 ms 42836 KB Output is correct
4 Correct 25 ms 43196 KB Output is correct
5 Correct 25 ms 43220 KB Output is correct
6 Correct 23 ms 42776 KB Output is correct
7 Correct 25 ms 43252 KB Output is correct
8 Correct 24 ms 43192 KB Output is correct
9 Correct 23 ms 42772 KB Output is correct
10 Correct 28 ms 42828 KB Output is correct
11 Correct 315 ms 63020 KB Output is correct
12 Correct 296 ms 64652 KB Output is correct
13 Correct 319 ms 67692 KB Output is correct
14 Correct 380 ms 76600 KB Output is correct
15 Correct 395 ms 80300 KB Output is correct
16 Correct 598 ms 102736 KB Output is correct
17 Correct 512 ms 106044 KB Output is correct
18 Correct 513 ms 103176 KB Output is correct
19 Correct 517 ms 107752 KB Output is correct
20 Correct 283 ms 65316 KB Output is correct
21 Correct 230 ms 64324 KB Output is correct
22 Incorrect 473 ms 103320 KB Output isn't correct
23 Halted 0 ms 0 KB -