oj.uz

Submission #405683

# Submission time Handle Problem Language Result Execution time Memory
405683 2021-05-16T17:38:55 Z Hazem One-Way Streets (CEOI17_oneway) C++14
100 / 100
 559 ms 58520 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 11 ms 14748 KB Output is correct
4 Correct 11 ms 14656 KB Output is correct
5 Correct 11 ms 14712 KB Output is correct
6 Correct 10 ms 14628 KB Output is correct
7 Correct 11 ms 14788 KB Output is correct
8 Correct 11 ms 14664 KB Output is correct
9 Correct 11 ms 14688 KB Output is correct
10 Correct 10 ms 14668 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 11 ms 14748 KB Output is correct
4 Correct 11 ms 14656 KB Output is correct
5 Correct 11 ms 14712 KB Output is correct
6 Correct 10 ms 14628 KB Output is correct
7 Correct 11 ms 14788 KB Output is correct
8 Correct 11 ms 14664 KB Output is correct
9 Correct 11 ms 14688 KB Output is correct
10 Correct 10 ms 14668 KB Output is correct
11 Correct 418 ms 45704 KB Output is correct
12 Correct 430 ms 47396 KB Output is correct
13 Correct 449 ms 49696 KB Output is correct
14 Correct 520 ms 51456 KB Output is correct
15 Correct 529 ms 51660 KB Output is correct
16 Correct 542 ms 49152 KB Output is correct
17 Correct 498 ms 52020 KB Output is correct
18 Correct 530 ms 49084 KB Output is correct
19 Correct 477 ms 53940 KB Output is correct
20 Correct 406 ms 47788 KB Output is correct
21 Correct 345 ms 46132 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 11 ms 14748 KB Output is correct
4 Correct 11 ms 14656 KB Output is correct
5 Correct 11 ms 14712 KB Output is correct
6 Correct 10 ms 14628 KB Output is correct
7 Correct 11 ms 14788 KB Output is correct
8 Correct 11 ms 14664 KB Output is correct
9 Correct 11 ms 14688 KB Output is correct
10 Correct 10 ms 14668 KB Output is correct
11 Correct 418 ms 45704 KB Output is correct
12 Correct 430 ms 47396 KB Output is correct
13 Correct 449 ms 49696 KB Output is correct
14 Correct 520 ms 51456 KB Output is correct
15 Correct 529 ms 51660 KB Output is correct
16 Correct 542 ms 49152 KB Output is correct
17 Correct 498 ms 52020 KB Output is correct
18 Correct 530 ms 49084 KB Output is correct
19 Correct 477 ms 53940 KB Output is correct
20 Correct 406 ms 47788 KB Output is correct
21 Correct 345 ms 46132 KB Output is correct
22 Correct 526 ms 53052 KB Output is correct
23 Correct 524 ms 50248 KB Output is correct
24 Correct 559 ms 50184 KB Output is correct
25 Correct 505 ms 58520 KB Output is correct
26 Correct 506 ms 52384 KB Output is correct
27 Correct 514 ms 50360 KB Output is correct
28 Correct 115 ms 17688 KB Output is correct
29 Correct 430 ms 48308 KB Output is correct
30 Correct 398 ms 48320 KB Output is correct
31 Correct 435 ms 49076 KB Output is correct
32 Correct 387 ms 46560 KB Output is correct