제출 #990620

#제출 시각아이디문제언어결과실행 시간메모리
990620groguOne-Way Streets (CEOI17_oneway)C++14
100 / 100
529 ms93756 KiB
    // __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;
    ll csz = 0;
    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]);
          	else low[u] = min(low[u],in[s]);
        }
        if(u==par) return;
        if(moze&&low[u]>in[par]){
            ++csz;
            while(stk.size()){
                ll to = stk.top();
                stk.pop();
                dsu[to] = csz;
                if(to==u) break;
            }
        }
    }
    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);
        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;
    }

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int main()':
oneway.cpp:152:14: warning: variable 'moe' set but not used [-Wunused-but-set-variable]
  152 |         bool moe = 1;
      |              ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...