제출 #585283

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

oneway

#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])cycle[id]=true,dp[s]++,dp[x]--;
        else if(!vis[x])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;
}

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

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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40