oj.uz

Submission #252023

# Submission time Handle Problem Language Result Execution time Memory
252023 2020-07-23T18:15:33 Z win11905 One-Way Streets (CEOI17_oneway) C++11
0 / 100
 2 ms 2688 KB 
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5+5;

int n, m, k;
int x[N], y[N];
vector<int> g[N];
bool check[N], checkEdge[N];
char ans[N];
int d1[N], d2[N];

void dfs(int u, int p) {
    check[u] = true;
    for(int e : g[u]) {
        int v = u ^ x[e] ^ y[e];
        if(v == p) continue;
        if(!check[v]) {
            dfs(v, u);
            checkEdge[e] = true;
        } else {
            if(x[e] == u) {
                swap(x[e], y[e]);
            }
        }
    }
}

void find_answer(int u, int p) {
    check[u] = false;
    for(int e : g[u]) if(checkEdge[e]) {
        int v = u ^ x[e] ^ y[e];
        if(v == p) continue; 
        ans[e] = 'B';
        find_answer(v, u);
        d1[u] += d1[v], d2[u] += d2[v];
        if(d1[v] || !d2[v]) {
            continue;
        }
        ans[e] = d2[v] < 0 ? 'L' : 'R';
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; ++i) {
        scanf("%d %d", &x[i], &y[i]);
        g[x[i]].emplace_back(i), g[y[i]].emplace_back(i);
    }
    for(int i = 1; i <= n; ++i) if(!check[i]){
        dfs(i, 0);
    }
    for(int i = 0; i < m; ++i) if(!checkEdge[i]) {
        ans[i] = 'B';
        d1[x[i]]++, d2[y[i]]--;
    }  
    scanf("%d", &k);
    for(int i = 0, a, b; i < k; ++i) {
        scanf("%d %d", &a, &b);
        d2[a]++, d2[b]--;
    }
    for(int i = 1; i <= n; ++i) if(check[i]) {
        find_answer(i, 0);       
    }
    puts(ans);
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x[i], &y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
oneway.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -