Submission #960356

#	Time	Username	Problem	Language	Result	Execution time	Memory
960356		noyancanturk	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	6488 KiB

oneway

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
#define int int64_t
#define pb push_back
    
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=0;
vector<pii>v[lim];

int dfs(int node,int par){
    tin[node]=tt++;
    int seen=tin[node];
    int parind=lim-1;
    for(int j=0;j<size(v[node]);j++){
        if(v[node][j].first==par){
            parind=v[node][j].second;
            continue;
        }
        if(!tin[v[node][j].first]){
            seen=min(seen,dfs(v[node][j].first,node));
        }else{
            seen=min(seen,tin[v[node][j].first]);
        }
    }
    if(seen==tin[node]){
        isbridge[parind]=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];

int compdfs(int node,int par,int camefrom=lim-1){
    for(auto[j,i]:to[node]){
        if(j!=par){
            vals[node]+=compdfs(j,node,i);
        }
    }
    if(0<vals[node]){
        ans[camefrom]='R';
    }
    if(vals[node]<0){
        ans[camefrom]='L';
    }
    //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,0);
        }
    }
    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<<" | "<<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});
        }
    }
    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]--;
    }
    compdfs(1,0);
    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();
    }
}

Compilation message (stderr)

oneway.cpp: In function 'int64_t dfs(int64_t, int64_t)':
oneway.cpp:25: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]
   25 |     for(int j=0;j<size(v[node]);j++){
      |                 ~^~~~~~~~~~~~~~
oneway.cpp: In function 'void groupall(int64_t)':
oneway.cpp:46: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]
   46 |     for(int j=0;j<size(v[node]);j++){
      |                 ~^~~~~~~~~~~~~~

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