Submission #252022

#	Time	Username	Problem	Language	Result	Execution time	Memory
252022		win11905	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	2 ms	2688 KiB

oneway

#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;
        }
        if((d2[v] < 0) ^ (x[e] == u)) {
            ans[e] = 'L';
        } else {
            ans[e] = '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 (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:51: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:53: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:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
oneway.cpp:65: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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40