Submission #162299

#	Time	Username	Problem	Language	Result	Execution time	Memory
162299		karma	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	138 ms	28184 KiB

oneway

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(2e5) + 7;

typedef pair<int, int> pii;
struct TEdge{int u, v; bool del;} e[N];
int low[N], num[N], Time = 0, br[N], lab[N], cnt = 0;
vector<int> ver, a[N];
vector<pii> g[N];
int n, m, u, v, q, c[N], f[N], vis[N];
string s;

void DFS(int u) {
    low[u] = num[u] = ++Time;
    for(int i: a[u]) {
       if(e[i].del) continue;
       e[i].del = 1;
       int v = e[i].u ^ e[i].v ^ u;
       if(!num[v]) {
         int cur = ver.size();
         DFS(v);
         low[u] = min(low[u], low[v]);
         if(low[v] >= num[v]) {
            br[i] = 1; ++cnt;
            while(int(ver.size()) > cur) lab[ver.back()] = cnt, ver.pop_back();
         }
       } else low[u] = min(low[u], num[v]);
    }
    ver.pb(u);
}

void dfs(int u) {
    vis[u] = 1;
    for(auto lst: g[u]) {
        if(vis[lst.fi]) continue;
        dfs(lst.fi);
        f[u] += f[lst.fi];
        if(f[lst.fi] < 0) s[lst.se - 1] = (lab[e[lst.se].u] == u? 'R': 'L');
        if(f[lst.fi] == 0) s[lst.se - 1] = 'B';
        if(f[lst.fi] > 0) s[lst.se - 1] = (lab[e[lst.se].u] == u? 'L': 'R');
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> u >> v;
        a[u].pb(i), a[v].pb(i);
        e[i] = {u, v, 0};
    }
    for(int i = 1; i <= n; ++i) {
        if(!lab[i]) {
            DFS(i); ++cnt;
            while(ver.size()) lab[ver.back()] = cnt, ver.pop_back();
        }
    }
    cin >> q;
    while(q --) {
        cin >> u >> v;
        ++c[u], --c[v];
    }
    s.resize(m);
    for(int i = 1; i <= m; ++i) {
        if(!br[i]) s[i - 1] = 'B';
        g[lab[e[i].u]].pb(mp(lab[e[i].v], i));
        g[lab[e[i].v]].pb(mp(lab[e[i].u], i));
    }
    for(int i = 1; i <= n; ++i) f[lab[i]] += c[i];
    for(int i = 1; i <= n; ++i)
        if(!vis[i]) dfs(i);
    cout << s;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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