제출 #585296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585296		hibiki	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	181 ms	18888 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

int n,m,p;
int l[100005], r[100005], cnt[100005], ask[100005], ans[100005];
vector<int> v[100005];
bool reach[100005], reach2[100005];
map<pair<int,int>, int> mp;

void dfs(int nw, int fa)
{
    reach[nw] = true;
    for(auto idx: v[nw])
    {
        int go = nw ^ l[idx] ^ r[idx];
        if(go == fa) continue;
        if(reach[go] && ans[idx] != 3)ans[idx] = 3, cnt[go]--, cnt[nw]++;
        else if(!reach[go]) dfs(go, nw);
    }
}

void dfs2(int nw, int fa)
{
    reach2[nw] = true;
    for(auto idx: v[nw])
    {
        int go = nw ^ l[idx] ^ r[idx];
        if(go == fa || reach2[go]) continue;
        dfs2(go, nw);
        if(cnt[go] > 0 || ask[go] == 0 || ans[idx] == 3) ans[idx] = 3;
        else if(ask[go] > 0)
        {
            if(l[idx] ^ nw)
                ans[idx] = 2;
            else
                ans[idx] = 1;
        }
        else if(ask[go] < 0)
        {
            if(l[idx] ^ nw)
                ans[idx] = 1;
            else
                ans[idx] = 2;
        }
        ask[nw] += ask[go];
        cnt[nw] += cnt[go];
    }
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d %d",&l[i],&r[i]);
        if(!mp.count({min(l[i],r[i]),max(l[i],r[i])}))
        {
            v[l[i]].pb(i);
            v[r[i]].pb(i);
        }
        mp[{min(l[i],r[i]),max(l[i],r[i])}]++;
    }
    for(int i = 1; i <= n; i++)
        if(!reach[i])
            dfs(i, -1);
    scanf("%d",&p);
    while(p--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        ask[a]++;
        ask[b]--;
    }
    for(int i = 1; i <= n; i++)
        if(!reach2[i])
            dfs2(i, -1);
    for(int i = 0; i < m; i++)
        if(mp[{min(l[i],r[i]),max(l[i],r[i])}] > 1)
            ans[i] = 3;
    char wd[] = {'0', 'L', 'R', 'B'};
    for(int i = 0; i < m; i++)
        printf("%c",wd[ans[i]]);
    printf("\n");
    return 0;
}

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

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

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