제출 #960374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960374		noyancanturk	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	74 ms	25532 KiB

oneway

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define pb push_back
#define int int64_t
    
const int lim=1e5+100;
int mod=998244353;
//const int mod=(1ll<<61)-1;
 
using pii=pair<int,int>;

bool isbridge[lim];
int tin[lim],tt=1;
vector<pii>v[lim];

int dfs(int node,int camefrom=lim-1){
    tin[node]=tt++;
    int seen=INT_MAX;
    for(int j=0;j<size(v[node]);j++){
        if(v[node][j].second^camefrom){
            if(!tin[v[node][j].first]){
                seen=min(seen,dfs(v[node][j].first,v[node][j].second));
            }else{
                seen=min(seen,tin[v[node][j].first]);
            }
        }
    }
    //cerr<<node<<" "<<tin[node]<<" "<<seen<<"\n";
    if(tin[node]<=seen){
        isbridge[camefrom]=1;
    }
    return seen;
}

int comp[lim],cnt=1;

void groupall(int node){
    comp[node]=cnt;
    for(int j=0;j<size(v[node]);j++){
        if(!comp[v[node][j].first]&&!isbridge[v[node][j].second]){
            groupall(v[node][j].first);
        }
    }
}

vector<pii>to[lim];
vector<pii>edges;

int vals[lim];
char ans[lim];
bool vis[lim];

int compdfs(int node,int camefrom=lim-1){
    vis[node]=1;
    //cerr<<node<<" "<<camefrom<<" visiting\n";
    for(auto[j,i]:to[node]){
        if(i^camefrom){
            vals[node]+=compdfs(j,i);
        }
    }
    if(0<vals[node]){
        ans[camefrom]=(node==comp[edges[camefrom].first])?'R':'L';
    }
    if(vals[node]<0){
        ans[camefrom]=(node==comp[edges[camefrom].first])?'L':'R';
    }
    //cerr<<node<<" "<<vals[node]<<"\n";
    return vals[node];
}

void solve(){
    int n,m;
    cin>>n>>m;
    edges.pb({0,0});
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v[x].pb({y,i});
        v[y].pb({x,i});
        edges.pb({x,y});
        //cerr<<i<<" | "<<x<<" "<<y<<"\n";
    }
    for(int i=1;i<=n;i++){
        if(!tin[i]){
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(!comp[i]){
            groupall(i);
            cnt++;
        }
    }
    for(int i=1;i<=m;i++){
        if(isbridge[i]){
            //cerr<<i<<"\n";
            //cerr<<i<<" | "<<edges[i].first<<" "<<edges[i].second<<" | new bridge\n";
            to[comp[edges[i].first]].pb({comp[edges[i].second],i});
            to[comp[edges[i].second]].pb({comp[edges[i].first],i});
        }
    }
    //cerr<<"ok\n";
    for(int i=1;i<=m;i++){
        ans[i]='B';
    }
    /*
    for(int i=1;i<=n;i++){
        cerr<<comp[i]<<" ";
    }cerr<<"\n";
    for(int i=1;i<=cnt;i++){
        cerr<<i<<" :\n";
        for(auto[j,c]:to[i]){
            cerr<<j<<" "<<c<<"\n";
        }cerr<<"\n";
    }
    */
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int x,y;
        cin>>x>>y;
        int aa=comp[x],bb=comp[y];
        vals[aa]++,vals[bb]--;
    }
    for(int i=1;i<=cnt;i++){
        if(!vis[i])compdfs(i);
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i];
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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

oneway.cpp: In function 'int64_t dfs(int64_t, int64_t)':
oneway.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=0;j<size(v[node]);j++){
      |                 ~^~~~~~~~~~~~~~
oneway.cpp: In function 'void groupall(int64_t)':
oneway.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int j=0;j<size(v[node]);j++){
      |                 ~^~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40