oj.uz

답안 #79321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79321 2018-10-12T08:30:01 Z Saboon One-Way Streets (CEOI17_oneway) C++14
0 / 100
 4 ms 2740 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
const int mod = 1e9 + 7;

bool visited[maxn], mark[maxn];
int dp[maxn], h[maxn], a[maxn], b[maxn], from[maxm];

vector <pii> g[maxn];

void dfs (int v, int par = -1, int idx = 0) {
    mark[idx] = 1;
    visited[v] = 1;
    dp[v] = h[v];
    for (auto u : g[v]) {
        if (!mark[u.S] and u.F == par)
            dp[v] = h[v] - 1;
        if (!visited[u.F]) {
            h[u.F] = h[v] + 1;
            dfs (u.F, v, u.S);
            a[v] += a[u.F];
            b[v] += b[u.F];
            dp[v] = min (dp[v], dp[u.S]);
        }
        else if (u.F != par)
            dp[v] = min (dp[v], h[u.F]);
    }
    if (par != -1 and dp[v] == h[v]) {
        if (a[v] > b[v]) {
            from[idx] = v;
        }
        else {
            from[idx] = par;
        }
    }
}

pii edge[maxm];

int main() {
    ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int v, u;
        cin >> v >> u;
        g[v].PB ({u, i});
        g[u].PB ({v, i});
        edge[i] = {v, u};
    }
    int p;
    cin >> p;
    for (int i = 1; i <= p; i++) {
        int x, y;
        cin >> x >> y;
        a[x] ++;
        b[y] ++;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs (i);
        }
    }
    for (int i = 1; i <= m; i++) {
        if (from[i] == edge[i].F)
            cout << "R";
        else if (from[i] == edge[i].S)
            cout << "L";
        else
            cout << "B";
    }
    cout << endl;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2740 KB Output isn't correct
2 Halted 0 ms 0 KB -