oj.uz

Submission #585280

# Submission time Handle Problem Language Result Execution time Memory
585280 2022-06-28T14:11:57 Z krit3379 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 2 ms 2672 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005

struct A{
    int a,flag,id;
};

int dp[N];
vector<A> g[N];
bitset<N> vis,cycle,both,res;
map<pair<int,int>,int> mp;
pair<int,int> edge[N];

void dfs(int s,int f){
    vis[s]=true;
    for(auto [x,flag,id]:g[s]){
        if(x==f)continue;
        if(vis[x])cycle[id]=true,dp[s]++,dp[x]--;
        else dfs(x,s);
    }
}

void sol1(int s,int f){
    vis[s]=true;
    for(auto [x,flag,id]:g[s]){
        if(x==f||vis[x])continue;
        sol1(x,s);
        if(dp[x])cycle[id]=true;
        dp[s]+=dp[x];
    }
}

void sol2(int s,int f){
    vis[s]=true;
    for(auto [x,flag,id]:g[s]){
        if(x==f||vis[x])continue;
        sol2(x,s);
        if(dp[x]){
            bool f=dp[x]>0?true:false;
            res[id]=f^flag;
        }
        else both[id]=true;
        dp[s]+=dp[x];
    }
}

int main(){
    int n,m,p,i,a,b;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d %d",&a,&b);
        if(!mp.count(minmax(a,b))){
            g[a].push_back({b,0,i});
            g[b].push_back({a,1,i});
        }
        mp[minmax(a,b)]++;
        edge[i]={a,b};
    }
    for(i=1;i<=n;i++)if(!vis[i])dfs(i,0);
    vis=0;
    for(i=1;i<=n;i++)if(!vis[i])sol1(i,0);
    vis=0;
    for(i=1;i<=n;i++)dp[i]=0;
    scanf("%d",&p);
    while(p--){
        scanf("%d %d",&a,&b);
        dp[a]++,dp[b]--;
    }
    vis=0;
    for(i=1;i<=n;i++)if(!vis[i])sol2(i,0);
    for(i=1;i<=m;i++){
        if(cycle[i]||both[i]||mp[minmax(edge[i].first,edge[i].second)]>1)printf("B");
        else if(res[i])printf("L");
        else printf("R");
    }
    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d",&p);
      |     ~~~~~^~~~~~~~~
oneway.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2672 KB Output isn't correct
2 Halted 0 ms 0 KB -