Submission #405683

#	Time	Username	Problem	Language	Result	Execution time	Memory
405683		Hazem	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	559 ms	58520 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 3e5+10;
const int M = 3e2+10;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;   
const double PI = 3.141592653589793;

map<pair<int,int>,char>mp;
map<pii,int>mp2;

vector<int>adj[N],adj2[N];
vector<pii>edges;
int val[N],vis[N],dp[N];

void dfs(int i,int pre){

    for(auto x:adj[i]){
        if(vis[x]){
            if(x!=pre)   
                mp[{i,x}] = mp[{x,i}] = 'B';

            continue;
        }

        vis[x] = vis[i]+1;     
        adj2[i].push_back(x);
        adj2[x].push_back(i);
        
        dfs(x,i);
    }

    for(auto x:adj[i]){
        if(x==pre)continue;
        
        if(vis[x]<vis[i]){
            dp[i]++;
            continue;
        }

        if(vis[x]>vis[i]+1){
            dp[i]--;
            continue;
        }

        if(dp[x]||mp2[{i,x}]>1)
            mp[{i,x}] = mp[{x,i}] = 'B';

        dp[i] += dp[x];
    }
}

void dfs2(int i,int pre){

    for(auto x:adj2[i]){
        if(x==pre)continue;

        dfs2(x,i);

        val[i] += val[x];
        if(dp[x]||mp2[{i,x}]>1)continue;
        
        if(val[x]<0)
            mp[{i,x}] = 'R',mp[{x,i}] = 'L';
        else 
        if(val[x]>0)
            mp[{i,x}] = 'L',mp[{x,i}] = 'R';
        else 
            mp[{i,x}] = mp[{x,i}] = 'B';
    }
}

int main(){

    //freopen("out.txt","w",stdout);

    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){
        
        int u,v;
        scanf("%d%d",&u,&v);
        edges.push_back({u,v});

        mp2[{u,v}]++;
        mp2[{v,u}]++;

        if(mp2[{u,v}]>1)
            continue;
                
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int q;
    scanf("%d",&q);

    while(q--){
        int u,v;
        scanf("%d%d",&u,&v);
        val[u]++;
        val[v]--;
    }

    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        vis[i] = 1;
        dfs(i,0);
        dfs2(i,0);
    }
    
    for(auto x:edges)
        cout<<mp[x];
}   

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
oneway.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
oneway.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
oneway.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

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