oj.uz

Submission #631824

# Submission time Handle Problem Language Result Execution time Memory
631824 2022-08-18T20:28:40 Z NintsiChkhaidze One-Way Streets (CEOI17_oneway) C++14
100 / 100
 388 ms 38324 KB 
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
 
const int N = 100005;
int tin[N],low[N],a[N],b[N],ID[N],in[N],out[N],dp[N],d[25][N],n1[N],n2[N];
int t[5][4*N],op[N],cl[N];
bool O[N],C[N],bridge[N],vis[N];
vector <int> adj[N],vec[N];
vector <pair<int,int> > v[N];
int idx,cnt,n;
 
//sworia upd
void upd(int id,int h,int l,int r,int idx,int val){
    if (l == r){
        t[id][h] += val;
        return;
    }
    if (idx > ((l + r)>>1)) upd(id,right,idx,val);
    else upd(id,left,idx,val);
    
    t[1][h] = max(t[1][h*2],t[1][h*2+1]);
    t[2][h] = max(t[2][h*2],t[2][h*2+1]);
}
//sworia get
int get(int id,int h,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return t[id][h];
    return max(get(id,left,L,R),get(id,right,L,R));
}
 
//sworia - bridgebis povna
void dfs(int x,int par){
    vis[x] = 1;
    tin[x] = low[x] = cnt++;
    for (auto [to,id]: v[x]){
        if (to == par) continue;
        if (vis[to]){
            low[x] = min(low[x], tin[to]);
        }else{
            dfs(to,x);
            low[x] = min(low[x], low[to]);
            if (low[to] > tin[x]) bridge[id] = 1;
        }
    }
}

//sworia axali xis ageba 
void dfs1(int x){
    ID[x] = idx;
    vis[x] = 1;
    for (auto [to,id]: v[x]){
        if (!vis[to] && !bridge[id]) dfs1(to);
        else if (!vis[to] && bridge[id]) vec[idx].pb(to);
    }
}

//sworia
void dfs2(int x,int par){
    vis[x] = 1;
    in[x] = ++cnt;
    d[0][x] = par;
    dp[x] = dp[par] + 1;
    for (int to: adj[x])
        if (!vis[to]) dfs2(to,x);
    out[x] = cnt;
}

//?
void dfs3(int x,int par){
    vis[x] = 1;
    for (int to: adj[x]) 
        if (!vis[to]) dfs3(to,x);

    upd(1,1,1,n,in[x],op[x]);
    upd(2,1,1,n,in[x],cl[x]);
    for (int id: vec[x]) {
        upd(1,1,1,n,in[n1[id]],-1);
        upd(2,1,1,n,in[n2[id]],-1);
    }

    int u = get(1,1,1,n,in[x],out[x]);
    O[x] = (u > 0);
    u = get(2,1,1,n,in[x],out[x]);
    C[x] = (u > 0);
}

//sworia lca
int lca(int x,int y){
    if (dp[x] < dp[y]) swap(x,y);
    for (int j = 18; j >= 0; j--)
        if (dp[d[j][x]] >= dp[y]) x = d[j][x];
    if (x == y) return x;
    for (int j = 18; j >=0; j--)
        if(d[j][x] != d[j][y]) x = d[j][x],y = d[j][y];
    return d[0][x];
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int m;
    cin>>n>>m;
    for (int i = 1; i <= m; i++){
        cin>>a[i]>>b[i];
        v[a[i]].pb({b[i],i});
        v[b[i]].pb({a[i],i});
    }
 
    for (int i= 1; i <= n; i++)
        if (!vis[i]) dfs(i,i); 
 
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(),v[i].end());
        for (int j = 1; j < v[i].size(); j++)
            if (v[i][j].f == v[i][j - 1].f) bridge[v[i][j].s] = bridge[v[i][j - 1].s] = 0;
    }
    
    for (int i= 1; i <= n; i++) 
        vis[i] = 0;
    idx = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) idx++,dfs1(i);
    
    for (int i = 1; i <= n; i++)
        for (int x: vec[i])
            adj[i].pb(ID[x]),adj[ID[x]].pb(i);
            // cout<<i<<" "<<ID[x]<<endl;
            
    for (int i = 1; i <= n; i++)
        vec[i].clear(),vis[i] = 0;
    
    cnt=0;
    for (int i = 1; i <= n; i++) 
        if (!vis[i]) dfs2(i,i);
        
    for (int j = 1; j < 19; j++)
        for (int i = 1; i <= n; i++)
            d[j][i] = d[j - 1][d[j - 1][i]];

    int k;
    cin>>k;
    for (int i = 1; i <= k; i++){
        cin>>n1[i]>>n2[i];
        n1[i] = ID[n1[i]],n2[i] = ID[n2[i]];
        int c = lca(n1[i],n2[i]);
        vec[c].pb(i);
        // cout<<n1[i]<<" "<<n2[i]<<" lca = "<<c<<endl;
        op[n1[i]]++;
        cl[n2[i]]++;
        // cout<<n1[i]<<" ^ "<<op[n1[i]]<<endl;
    }
    
    for (int i = 1; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++) if (!vis[i]) dfs3(i,i);
    
    for (int i = 1; i <= m; i++){
        if (!bridge[i]) cout<<'B';
        else{
            int x = ID[a[i]],y = ID[b[i]];
            if (dp[x] >= dp[y]){
                if(O[x] && !C[x]) cout<<'R';
                else if (!O[x] && C[x]) cout<<'L';
                else cout<<'B';
            }else{
                if(O[y] && !C[y]) cout<<'L';
                else if (!O[y] && C[y]) cout<<'R';
                else cout<<'B';
            }
        }
    }
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'int main()':
oneway.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int j = 1; j < v[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 4 ms 7764 KB Output is correct
5 Correct 4 ms 7764 KB Output is correct
6 Correct 4 ms 7584 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7784 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 5 ms 7636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 4 ms 7764 KB Output is correct
5 Correct 4 ms 7764 KB Output is correct
6 Correct 4 ms 7584 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7784 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 5 ms 7636 KB Output is correct
11 Correct 47 ms 15824 KB Output is correct
12 Correct 63 ms 17740 KB Output is correct
13 Correct 85 ms 21268 KB Output is correct
14 Correct 141 ms 26444 KB Output is correct
15 Correct 111 ms 27732 KB Output is correct
16 Correct 151 ms 30728 KB Output is correct
17 Correct 163 ms 32524 KB Output is correct
18 Correct 147 ms 31180 KB Output is correct
19 Correct 158 ms 33616 KB Output is correct
20 Correct 65 ms 19560 KB Output is correct
21 Correct 63 ms 19516 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7508 KB Output is correct
3 Correct 5 ms 7636 KB Output is correct
4 Correct 4 ms 7764 KB Output is correct
5 Correct 4 ms 7764 KB Output is correct
6 Correct 4 ms 7584 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7784 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 5 ms 7636 KB Output is correct
11 Correct 47 ms 15824 KB Output is correct
12 Correct 63 ms 17740 KB Output is correct
13 Correct 85 ms 21268 KB Output is correct
14 Correct 141 ms 26444 KB Output is correct
15 Correct 111 ms 27732 KB Output is correct
16 Correct 151 ms 30728 KB Output is correct
17 Correct 163 ms 32524 KB Output is correct
18 Correct 147 ms 31180 KB Output is correct
19 Correct 158 ms 33616 KB Output is correct
20 Correct 65 ms 19560 KB Output is correct
21 Correct 63 ms 19516 KB Output is correct
22 Correct 367 ms 35220 KB Output is correct
23 Correct 319 ms 33700 KB Output is correct
24 Correct 337 ms 34000 KB Output is correct
25 Correct 388 ms 38324 KB Output is correct
26 Correct 359 ms 35060 KB Output is correct
27 Correct 324 ms 33836 KB Output is correct
28 Correct 63 ms 13100 KB Output is correct
29 Correct 105 ms 21688 KB Output is correct
30 Correct 111 ms 21912 KB Output is correct
31 Correct 114 ms 22516 KB Output is correct
32 Correct 185 ms 27012 KB Output is correct