oj.uz

Submission #558456

# Submission time Handle Problem Language Result Execution time Memory
558456 2022-05-07T11:42:40 Z urosk One-Way Streets (CEOI17_oneway) C++14
100 / 100
 1105 ms 106080 KB 
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

#define maxn 100005
ll n,m;
map<pll,ll> cnt;
map<pll,bool> ans;
ll con[maxn];
vector<ll> g[maxn];
ll in[maxn];
vector<pll> edge;
ll it = 1;
ll low[maxn];
bool vis[maxn];
stack<ll> stk;
map<pll,bool> bio;
map<pll,bool> most;
ll dsu[maxn];
ll comp = 1;
void dfs(ll u,ll par){
    low[u] = in[u] = it++;
    vis[u] = 1;
    stk.push(u);
    bool moze =1;
    if(cnt[{u,par}]>1) moze = 0;
    for(ll s : g[u]){
        if(s==par){
            if(cnt[{u,par}]==1) continue;
            continue;
        }
        if(!vis[s]) dfs(s,u);
        low[u] = min(low[u],low[s]);
    }
    if(u==par) return;
    if(moze&&low[u]>in[par]){
        most[{u,par}] = 1;
        most[{par,u}] = 1;
    }
}
void dfs4(ll u,ll par){
    vis[u] = 1;
    dsu[u] =comp;
    for(ll s : g[u]){
        if(s==par) continue;
        if(most[{u,s}]) continue;
        if(vis[s]) continue;
        dfs4(s,u);
    }
}
ll root(ll x){
    while(x!=con[x]){
        con[x] = con[con[x]];
        x = con[x];
    }
    return x;
}
void upd(ll x,ll y){
    x = root(x);
    y = root(y);
    con[x] = con[y];
}
ll q;
#define lg 25
ll in2[maxn];
ll out2[maxn];
vector<ll> v[maxn];
ll st[maxn][lg];
void dfs2(ll u,ll par){
    vis[u] =1;
    st[u][0] = par;
    in2[u] = it++;
    for(ll s : v[u]){
        if(s==par) continue;
        dfs2(s,u);
    }
    out2[u] = it-1;
}
bool intree(ll x,ll y){
    return in2[x]>=in2[y]&&out2[y]>=out2[x];
}
ll lca(ll x,ll y){
    if(intree(x,y)) return y;
    if(intree(y,x)) return x;
    for(ll j = lg-1;j>=0;j--){
        if(!intree(x,st[y][j])) y = st[y][j];
    }
    return st[y][0];
}
map<pll,ll> mp;
ll poc[maxn];
ll kr[maxn];
void dfs3(ll u,ll par){
    vis[u] = 1;
    for(ll s : v[u]){
        if(s==par) continue;
        dfs3(s,u);
        poc[u]+=poc[s];
        kr[u]+=kr[s];
    }
    mp[{u,par}] = poc[u]-kr[u];
    mp[{par,u}] = poc[u]-kr[u];
}
map<pll,pll> tru;
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m;
    for(ll i = 1;i<=m;i++){
        ll x,y; cin >> x >> y;
        cnt[{x,y}]++;
        cnt[{y,x}]++;
        edge.pb({x,y});
        g[x].pb(y);
        g[y].pb(x);
    }
    fill(vis,vis+n+1,0);
    for(ll i = 1;i<=n;i++) if(vis[i]==0) dfs(i,i);
    fill(vis,vis+n+1,0);
    for(ll i = 1;i<=n;i++) if(vis[i]==0){dfs4(i,i);comp++;}
    iota(con+1,con+n+1,1);
    //here;
    //cerr<<"DSU: "<<endl;
    //ceri(dsu,1,n);
    for(pll p : edge){
        ll x = p.fi;
        ll y = p.sc;
        if(root(dsu[x])==root(dsu[y])) continue;
        tru[{x,y}] = {dsu[x],dsu[y]};
        tru[{y,x}] = {dsu[y],dsu[x]};
        v[dsu[x]].pb(dsu[y]);
        v[dsu[y]].pb(dsu[x]);
        upd(dsu[x],dsu[y]);
    }
    it = 1;
    fill(vis,vis+n+1,0);
    for(ll i = 1;i<=n;i++) if(vis[i]==0) dfs2(i,i);
    for(ll j = 1;j<lg;j++) for(ll i = 1;i<=n;i++) st[i][j] = st[st[i][j-1]][j-1];
    cin >> q;
    bool moe = 1;
    vector<pll> upit;
    for(ll i = 1;i<=q;i++){
        ll x,y; cin >> x >> y;
        upit.pb({x,y});
        x = dsu[x];
        y = dsu[y];
        if(x==y) continue;
        if(st[x][lg-1]!=st[y][lg-1]) moe = 0;
        poc[x]++;
        kr[y]++;
        ll z = lca(x,y);
        poc[z]--;
        kr[z]--;
        //cerr<<"lca: "<<x<< " "<<y<< " "<<z<<endl;
    }
    //here;
    //cerr<<"DSU: "<<endl;
    //ceri(dsu,1,n);
    fill(vis,vis+n+1,0);
    //for(ll i = 1;i<=n;i++) cerr<<poc[i]-kr[i]<<" ";
    //cerr<<endl;
    for(ll i = 1;i<=n;i++) if(vis[i]==0) dfs3(i,i);
    //for(ll i = 1;i<=n;i++) cerr<<poc[i]-kr[i]<<" ";
    //cerr<<endl;
    //here;
    for(ll ii = 0;ii<m;ii++){
        pll p = edge[ii];
        if(p.fi==p.sc){
            cout<<'B';
            continue;
        }
        if(cnt[p]>1) cout<<'B';
        else{
            if(dsu[p.fi]==dsu[p.sc]){
                cout<<'B';
                //cerr<<ii<<" "<<dsu[p.fi]<<endl;
                continue;
            }
            ll x = mp[tru[p]];
            if(x==0) cout<<'B';
            else if(x>0){
                if(in2[dsu[p.fi]]>in2[dsu[p.sc]]) cout<<'R';
                else cout<<'L';
            }else{
                if(in2[dsu[p.fi]]>in2[dsu[p.sc]]) cout<<'L';
                else cout<<'R';
            }
        }
    }
    cout<<endl;
	return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:157:10: warning: variable 'moe' set but not used [-Wunused-but-set-variable]
  157 |     bool moe = 1;
      |          ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 5 ms 5052 KB Output is correct
3 Correct 5 ms 5588 KB Output is correct
4 Correct 7 ms 5968 KB Output is correct
5 Correct 9 ms 5964 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 8 ms 5972 KB Output is correct
8 Correct 6 ms 5972 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 4 ms 5440 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 5 ms 5052 KB Output is correct
3 Correct 5 ms 5588 KB Output is correct
4 Correct 7 ms 5968 KB Output is correct
5 Correct 9 ms 5964 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 8 ms 5972 KB Output is correct
8 Correct 6 ms 5972 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 4 ms 5440 KB Output is correct
11 Correct 289 ms 42488 KB Output is correct
12 Correct 390 ms 46776 KB Output is correct
13 Correct 374 ms 54112 KB Output is correct
14 Correct 582 ms 68368 KB Output is correct
15 Correct 646 ms 73836 KB Output is correct
16 Correct 1060 ms 95236 KB Output is correct
17 Correct 836 ms 98120 KB Output is correct
18 Correct 1006 ms 95288 KB Output is correct
19 Correct 815 ms 100000 KB Output is correct
20 Correct 355 ms 50572 KB Output is correct
21 Correct 292 ms 49140 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 5 ms 5052 KB Output is correct
3 Correct 5 ms 5588 KB Output is correct
4 Correct 7 ms 5968 KB Output is correct
5 Correct 9 ms 5964 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 8 ms 5972 KB Output is correct
8 Correct 6 ms 5972 KB Output is correct
9 Correct 4 ms 5460 KB Output is correct
10 Correct 4 ms 5440 KB Output is correct
11 Correct 289 ms 42488 KB Output is correct
12 Correct 390 ms 46776 KB Output is correct
13 Correct 374 ms 54112 KB Output is correct
14 Correct 582 ms 68368 KB Output is correct
15 Correct 646 ms 73836 KB Output is correct
16 Correct 1060 ms 95236 KB Output is correct
17 Correct 836 ms 98120 KB Output is correct
18 Correct 1006 ms 95288 KB Output is correct
19 Correct 815 ms 100000 KB Output is correct
20 Correct 355 ms 50572 KB Output is correct
21 Correct 292 ms 49140 KB Output is correct
22 Correct 909 ms 100664 KB Output is correct
23 Correct 927 ms 97896 KB Output is correct
24 Correct 1105 ms 97992 KB Output is correct
25 Correct 885 ms 106080 KB Output is correct
26 Correct 953 ms 100040 KB Output is correct
27 Correct 919 ms 97972 KB Output is correct
28 Correct 97 ms 13772 KB Output is correct
29 Correct 386 ms 52572 KB Output is correct
30 Correct 318 ms 52716 KB Output is correct
31 Correct 401 ms 53360 KB Output is correct
32 Correct 384 ms 63688 KB Output is correct