제출 #477285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477285		julian33	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	272 ms	38480 KiB

oneway

#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]];
}

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

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40