Submission #585289

#	Time	Username	Problem	Language	Result	Execution time	Memory
585289		hibiki	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	2 ms	2644 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];

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;
        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]);
        v[l[i]].pb(i);
        v[r[i]].pb(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);
    char wd[] = {'0', 'L', 'R', 'B'};
    for(int i = 0; i < m; i++)
        printf("%c",wd[ans[i]]);
    printf("\n");
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d",&l[i],&r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
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:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

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