oj.uz

Submission #585296

# Submission time Handle Problem Language Result Execution time Memory
585296 2022-06-28T14:49:25 Z hibiki One-Way Streets (CEOI17_oneway) C++11
100 / 100
 181 ms 18888 KB 
#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;
}

Compilation message

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 123 ms 13244 KB Output is correct
12 Correct 131 ms 14072 KB Output is correct
13 Correct 150 ms 15096 KB Output is correct
14 Correct 171 ms 15776 KB Output is correct
15 Correct 176 ms 15944 KB Output is correct
16 Correct 169 ms 14344 KB Output is correct
17 Correct 146 ms 15928 KB Output is correct
18 Correct 157 ms 14368 KB Output is correct
19 Correct 134 ms 17124 KB Output is correct
20 Correct 131 ms 13772 KB Output is correct
21 Correct 116 ms 13172 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 123 ms 13244 KB Output is correct
12 Correct 131 ms 14072 KB Output is correct
13 Correct 150 ms 15096 KB Output is correct
14 Correct 171 ms 15776 KB Output is correct
15 Correct 176 ms 15944 KB Output is correct
16 Correct 169 ms 14344 KB Output is correct
17 Correct 146 ms 15928 KB Output is correct
18 Correct 157 ms 14368 KB Output is correct
19 Correct 134 ms 17124 KB Output is correct
20 Correct 131 ms 13772 KB Output is correct
21 Correct 116 ms 13172 KB Output is correct
22 Correct 156 ms 15952 KB Output is correct
23 Correct 166 ms 14264 KB Output is correct
24 Correct 181 ms 14280 KB Output is correct
25 Correct 146 ms 18888 KB Output is correct
26 Correct 165 ms 15500 KB Output is correct
27 Correct 164 ms 14376 KB Output is correct
28 Correct 67 ms 4172 KB Output is correct
29 Correct 147 ms 13364 KB Output is correct
30 Correct 147 ms 13456 KB Output is correct
31 Correct 160 ms 13820 KB Output is correct
32 Correct 110 ms 14164 KB Output is correct