Submission #585282

#	Time	Username	Problem	Language	Result	Execution time	Memory
585282		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 ind[100005], edge[100005];
int l[100005], r[100005], cnt[100005], ask[100005], ans[100005], par[100005];
vector<int> v[100005];
bool reach[100005];
vector<int> leaves;

void dfs(int nw, int fa)
{
    if(sz(v[nw]) == 1 && v[nw][0] == fa) leaves.pb(nw);
    par[nw] = fa;
    ind[fa]++;
    for(auto idx: v[nw])
    {
        int go = nw ^ l[idx] ^ r[idx];
        if(go == fa || ans[idx] == 3) continue;
        if(reach[go])
            ans[idx] = 3, cnt[go]--, cnt[nw]++;
        else
            reach[go] = true, edge[go] = idx, dfs(go, nw);
    }
}

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])
            reach[i] = true, dfs(i, -1);
    }
    scanf("%d",&p);
    while(p--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        ask[a]++;
        ask[b]--;
    }
    queue<int> q;
    for(int i = 1; i <= n; i++)
        if(!ind[i])
            q.push(i);
    while(!q.empty())
    {
        int nw = q.front();
        q.pop();
        if(cnt[nw] > 0 || ask[nw] == 0)
            ans[edge[nw]] = 3;
        else if(ask[nw] > 0)
        {
            if(l[edge[nw]] ^ nw)
                ans[edge[nw]] = 1;
            else
                ans[edge[nw]] = 2;
        }
        else if(ask[nw] < 0)
        {
            if(l[edge[nw]] ^ nw)
                ans[edge[nw]] = 2;
            else
                ans[edge[nw]] = 1;
        }
        ind[par[nw]]--;
        if(!ind[par[nw]])
            q.push(par[nw]);
    }
    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:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d %d",&l[i],&r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d",&p);
      |     ~~~~~^~~~~~~~~
oneway.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

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