oj.uz

Submission #477285

# Submission time Handle Problem Language Result Execution time Memory
477285 2021-10-01T15:06:16 Z julian33 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 272 ms 38480 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=1e5+5; //make sure this is right
const int mod=1e9+7;

struct edge{
    int to,d,i;
};

vector<edge> graph[mxN],tree[mxN];
int lo[mxN],id[mxN],cur,up[mxN][20],sum[mxN][2],ht[mxN],ans[mxN],seen[mxN];

struct DSU{
    int uf[mxN];
    void init(){memset(uf,-1,sizeof(uf));}
    int find(int x){return uf[x]<0?x:uf[x]=find(uf[x]);}
    bool same(int x,int y){return find(x)==find(y);}
    void unite(int x,int y){
        x=find(x); y=find(y);
        if(x==y)
            return;
        if(uf[x]>uf[y])
            swap(x,y);
        if(sz(tree[y])>sz(tree[x]))
            swap(tree[y],tree[x]);
        for(auto &u:tree[y]){
            if(u.i==3){
                deb(x,y,u.to,u.d);
            }
            tree[x].pb(u);
        }
        tree[y].clear();
        uf[x]+=uf[y]; uf[y]=x;
    }   
} dsu;

void dfs(int at,int p){
    lo[at]=id[at]=++cur;
    for(auto &[to,d,i]:graph[at]){
        if(i==p)
            continue;
        if(!lo[to])
            dfs(to,i);
        if(lo[to]>id[at]){
            tree[dsu.find(at)].pb({dsu.find(to),d,i});
            tree[dsu.find(to)].pb({dsu.find(at),d^1,i});
        } else{
            dsu.unite(at,to);
        }
        mina(lo[at],lo[to]);
    }
}

void dfs2(int at,int p){
    up[at][0]=~p?p:at;
    for(int i=1;i<20;i++)
        up[at][i]=up[up[at][i-1]][i-1];
    for(auto &[to,d,i]:tree[at]){
        to=dsu.find(to);
        if(to==p)
            continue;
        ht[to]=ht[at]+1;
        dfs2(to,at);
    }
}

int jump(int a,int k){
    for(int i=0;i<20;i++){
        if(k&(1<<i))
            a=up[a][i];
    }
    return a;
}

int lca(int a,int b){
    if(ht[a]>ht[b])
        swap(a,b);
    b=jump(b,ht[b]-ht[a]);
    if(a==b)
        return a;
    for(int i=19;i>=0;i--){
        if(up[a][i]!=up[b][i]){
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}

void dfs3(int at,int p){
    seen[at]=1;
    for(auto &[to,d,i]:tree[at]){
        to=dsu.find(to);
        if(to==p)
            continue;
        dfs3(to,at);
        assert(!(sum[to][0] && sum[to][1]));
        if(sum[to][0]){
            ans[i]=d?1:2;
        } else if(sum[to][1]){
            ans[i]=d?2:1;
        }
        sum[at][0]+=sum[to][0];
        sum[at][1]+=sum[to][1];
    }
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    dsu.init();
    int n,m; cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        graph[a].pb({b,1,i});
        graph[b].pb({a,0,i});
    }
    for(int i=1;i<=n;i++){
        if(!lo[i]) dfs(i,-1);
    }
    for(int i=1;i<=n;i++){
        // deb(i,dsu.find(i));
        set<int> has;
        vector<edge> ac;
        for(auto &u:tree[i]){
            if(has.count(u.i))
                continue;
            has.insert(u.i);
            ac.pb(u);
        }
        swap(tree[i],ac);
    }
    for(int i=1;i<=n;i++){
        if(!ht[i] && sz(tree[i])) dfs2(i,-1);
    }
    int q; cin>>q;
    while(q--){
        int a,b; cin>>a>>b;
        a=dsu.find(a);
        b=dsu.find(b);
        int p=lca(a,b);
        sum[a][0]++;
        sum[p][0]--;
        sum[b][1]++;
        sum[p][1]--;
    }
    for(int i=1;i<=n;i++){
        if(!seen[i] && sz(tree[i])) dfs3(i,-1);
    }
    string s="BLR";
    for(int i=0;i<m;i++) cout<<s[ans[i]];
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:65:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for(auto &[to,d,i]:graph[at]){
      |               ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:84:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto &[to,d,i]:tree[at]){
      |               ^
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:118:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for(auto &[to,d,i]:tree[at]){
      |               ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5328 KB Output is correct
3 Correct 3 ms 5584 KB Output is correct
4 Correct 4 ms 5584 KB Output is correct
5 Correct 4 ms 5712 KB Output is correct
6 Correct 4 ms 5584 KB Output is correct
7 Correct 4 ms 5712 KB Output is correct
8 Correct 5 ms 5552 KB Output is correct
9 Correct 4 ms 5456 KB Output is correct
10 Correct 4 ms 5556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5328 KB Output is correct
3 Correct 3 ms 5584 KB Output is correct
4 Correct 4 ms 5584 KB Output is correct
5 Correct 4 ms 5712 KB Output is correct
6 Correct 4 ms 5584 KB Output is correct
7 Correct 4 ms 5712 KB Output is correct
8 Correct 5 ms 5552 KB Output is correct
9 Correct 4 ms 5456 KB Output is correct
10 Correct 4 ms 5556 KB Output is correct
11 Correct 45 ms 13768 KB Output is correct
12 Correct 70 ms 16688 KB Output is correct
13 Correct 66 ms 21972 KB Output is correct
14 Correct 84 ms 26784 KB Output is correct
15 Correct 115 ms 28136 KB Output is correct
16 Correct 175 ms 25488 KB Output is correct
17 Correct 148 ms 29548 KB Output is correct
18 Correct 146 ms 25676 KB Output is correct
19 Correct 185 ms 32544 KB Output is correct
20 Correct 55 ms 14108 KB Output is correct
21 Correct 50 ms 16948 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5328 KB Output is correct
3 Correct 3 ms 5584 KB Output is correct
4 Correct 4 ms 5584 KB Output is correct
5 Correct 4 ms 5712 KB Output is correct
6 Correct 4 ms 5584 KB Output is correct
7 Correct 4 ms 5712 KB Output is correct
8 Correct 5 ms 5552 KB Output is correct
9 Correct 4 ms 5456 KB Output is correct
10 Correct 4 ms 5556 KB Output is correct
11 Correct 45 ms 13768 KB Output is correct
12 Correct 70 ms 16688 KB Output is correct
13 Correct 66 ms 21972 KB Output is correct
14 Correct 84 ms 26784 KB Output is correct
15 Correct 115 ms 28136 KB Output is correct
16 Correct 175 ms 25488 KB Output is correct
17 Correct 148 ms 29548 KB Output is correct
18 Correct 146 ms 25676 KB Output is correct
19 Correct 185 ms 32544 KB Output is correct
20 Correct 55 ms 14108 KB Output is correct
21 Correct 50 ms 16948 KB Output is correct
22 Correct 272 ms 30760 KB Output is correct
23 Correct 196 ms 26588 KB Output is correct
24 Correct 211 ms 26824 KB Output is correct
25 Correct 237 ms 38480 KB Output is correct
26 Correct 217 ms 29756 KB Output is correct
27 Correct 222 ms 26844 KB Output is correct
28 Correct 37 ms 9740 KB Output is correct
29 Correct 68 ms 14280 KB Output is correct
30 Correct 81 ms 15660 KB Output is correct
31 Correct 80 ms 15308 KB Output is correct
32 Correct 137 ms 26868 KB Output is correct