oj.uz

Submission #563739

# Submission time Handle Problem Language Result Execution time Memory
563739 2022-05-18T05:00:32 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";
    }
   if(n > 100 && p > 100)return;
    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 22 ms 42580 KB Output is correct
2 Correct 22 ms 42564 KB Output is correct
3 Correct 23 ms 42844 KB Output is correct
4 Correct 25 ms 43176 KB Output is correct
5 Correct 25 ms 43220 KB Output is correct
6 Correct 24 ms 42808 KB Output is correct
7 Correct 25 ms 43220 KB Output is correct
8 Correct 28 ms 43220 KB Output is correct
9 Correct 24 ms 42836 KB Output is correct
10 Correct 25 ms 42788 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42580 KB Output is correct
2 Correct 22 ms 42564 KB Output is correct
3 Correct 23 ms 42844 KB Output is correct
4 Correct 25 ms 43176 KB Output is correct
5 Correct 25 ms 43220 KB Output is correct
6 Correct 24 ms 42808 KB Output is correct
7 Correct 25 ms 43220 KB Output is correct
8 Correct 28 ms 43220 KB Output is correct
9 Correct 24 ms 42836 KB Output is correct
10 Correct 25 ms 42788 KB Output is correct
11 Correct 271 ms 63080 KB Output is correct
12 Correct 283 ms 64668 KB Output is correct
13 Correct 308 ms 67772 KB Output is correct
14 Correct 405 ms 76588 KB Output is correct
15 Correct 380 ms 80272 KB Output is correct
16 Correct 506 ms 102828 KB Output is correct
17 Correct 483 ms 105960 KB Output is correct
18 Correct 487 ms 103212 KB Output is correct
19 Correct 485 ms 107692 KB Output is correct
20 Correct 257 ms 65268 KB Output is correct
21 Correct 220 ms 64356 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 42580 KB Output is correct
2 Correct 22 ms 42564 KB Output is correct
3 Correct 23 ms 42844 KB Output is correct
4 Correct 25 ms 43176 KB Output is correct
5 Correct 25 ms 43220 KB Output is correct
6 Correct 24 ms 42808 KB Output is correct
7 Correct 25 ms 43220 KB Output is correct
8 Correct 28 ms 43220 KB Output is correct
9 Correct 24 ms 42836 KB Output is correct
10 Correct 25 ms 42788 KB Output is correct
11 Correct 271 ms 63080 KB Output is correct
12 Correct 283 ms 64668 KB Output is correct
13 Correct 308 ms 67772 KB Output is correct
14 Correct 405 ms 76588 KB Output is correct
15 Correct 380 ms 80272 KB Output is correct
16 Correct 506 ms 102828 KB Output is correct
17 Correct 483 ms 105960 KB Output is correct
18 Correct 487 ms 103212 KB Output is correct
19 Correct 485 ms 107692 KB Output is correct
20 Correct 257 ms 65268 KB Output is correct
21 Correct 220 ms 64356 KB Output is correct
22 Execution timed out 3071 ms 115324 KB Time limit exceeded
23 Halted 0 ms 0 KB -