oj.uz

답안 #579939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579939 2022-06-20T10:15:03 Z dxz05 One-Way Streets (CEOI17_oneway) C++17
30 / 100
 3000 ms 47000 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

#include <random>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.000001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 1111;

int eu[N], ev[N];

vector<int> g[N];

int flag[N];

bool used[N];

set<pair<int, int>> bridges;

set<pair<int, int>> trash;

inline void bridge(int x, int y){
    if (trash.count(MP(x, y))) return;
    if (trash.count(MP(y, x))) return;
    bridges.insert(MP(x, y));
}

int tin[N], fup[N], timer = 0;
inline void dfs(int v, int p){
    tin[v] = fup[v] = ++timer;

    used[v] = true;
    for (int u : g[v]){
        if (u == p) continue;

        if (!used[u]){
            dfs(u, v);
            fup[v] = min(fup[v], fup[u]);
            if (fup[u] > tin[v]) bridge(u, v);
        } else {
            fup[v] = min(fup[v], tin[u]);
        }

    }
}

int p[N];

inline int find(int x){
    return (x == p[x] ? x : p[x] = find(p[x]));
}

inline void unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rng() & 1) swap(x, y);
    p[x] = y;
}

inline void bfs(int x, vector<int> &d){
    queue<int> q;
    fill(all(d), INF);
    d[x] = 0;
    q.push(x);

    while (!q.empty()){
        x = q.front();
        q.pop();
        for (int y : g[x]){
            if (d[y] == INF){
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
    }
}

map<pair<int, int>, int> mp;

void SetLeft(int x, int y){
    int i = mp.count(MP(x, y)) ? mp[MP(x, y)] : mp[MP(y, x)];
    flag[i] = 1;
}

void SetRight(int x, int y){
    int i = mp.count(MP(x, y)) ? mp[MP(x, y)] : mp[MP(y, x)];
    flag[i] = 2;
}

void solve(int TC) {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;

        eu[i] = x, ev[i] = y;

        if (mp.count(MP(x, y)) || mp.count(MP(y, x))){
            int ii = (mp.count(MP(x, y)) ? mp[MP(x, y)] : mp[MP(y, x)]);
            flag[i] = flag[ii] = 3;
            trash.insert(MP(x, y));
            continue;
        }

        if (x == y){
            flag[i] = 3;
            continue;
        }

        mp[MP(x, y)] = i;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    int q;
    cin >> q;

    vector<pair<int, int>> important;
    while (q--){
        int x, y;
        cin >> x >> y;
        important.emplace_back(x, y);
    }

    for (int i = 1; i <= n; i++){
        if (!used[i]) dfs(i, i);
    }

    for (int i = 1; i <= m; i++){
        int x = eu[i], y = ev[i];
        if (!bridges.count(MP(x, y)) && !bridges.count(MP(y, x))) flag[i] = 3;
    }

    auto _br = bridges;
    bridges.clear();
    for (auto now : _br){
        if (mp.find(now) == mp.end()) swap(now.first, now.second);
        bridges.insert(now);
    }

    iota(p + 1, p + n + 1, 1);

    for (int i = 1; i <= m; i++){
        if (flag[i] == 3) unite(eu[i], ev[i]);
    }

    for (int i = 1; i <= n; i++) g[i].clear();

    int root = n;

    for (int i = 1; i <= m; i++){
        int x = find(eu[i]), y = find(ev[i]);
        root = min({root, x, y});
        if (x != y){
            g[x].push_back(y);
            g[y].push_back(x);
        }
    }

    for (auto [x, y] : important){
        int X = x, Y = y;
        x = find(x), y = find(y);

        if (x == y) continue;

        vector<int> dx(n + 1), dy(n + 1);
        bfs(x, dx);
        bfs(y, dy);

        for (auto [u, v] : bridges){
            int U = u, V = v;

            u = find(u), v = find(v);

            int dist = min(dx[u] + dy[v], dx[v] + dy[u]) + 1;
            if (dist != dx[y]) continue;

            if (dx[u] + dy[v] + 1 == dist){
                SetRight(U, V);
            } else {
                SetLeft(U, V);
            }

        }

    }

    for (int i = 1; i <= m; i++){
        if (flag[i] == 0 || flag[i] == 3) cout << 'B';
        if (flag[i] == 1) cout << 'L';
        if (flag[i] == 2) cout << 'R';
    }

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
    //    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

#ifdef dddxxz
    cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

oneway.cpp: In function 'void solve(int)':
oneway.cpp:202:13: warning: unused variable 'X' [-Wunused-variable]
  202 |         int X = x, Y = y;
      |             ^
oneway.cpp:202:20: warning: unused variable 'Y' [-Wunused-variable]
  202 |         int X = x, Y = y;
      |                    ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 15 ms 23876 KB Output is correct
3 Correct 15 ms 23892 KB Output is correct
4 Correct 16 ms 24020 KB Output is correct
5 Correct 27 ms 24140 KB Output is correct
6 Correct 15 ms 23916 KB Output is correct
7 Correct 25 ms 24120 KB Output is correct
8 Correct 21 ms 24020 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 19 ms 23892 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 15 ms 23876 KB Output is correct
3 Correct 15 ms 23892 KB Output is correct
4 Correct 16 ms 24020 KB Output is correct
5 Correct 27 ms 24140 KB Output is correct
6 Correct 15 ms 23916 KB Output is correct
7 Correct 25 ms 24120 KB Output is correct
8 Correct 21 ms 24020 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 19 ms 23892 KB Output is correct
11 Correct 155 ms 34240 KB Output is correct
12 Correct 176 ms 35124 KB Output is correct
13 Correct 193 ms 36412 KB Output is correct
14 Correct 329 ms 39200 KB Output is correct
15 Correct 483 ms 40124 KB Output is correct
16 Correct 375 ms 45696 KB Output is correct
17 Execution timed out 3100 ms 47000 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 15 ms 23876 KB Output is correct
3 Correct 15 ms 23892 KB Output is correct
4 Correct 16 ms 24020 KB Output is correct
5 Correct 27 ms 24140 KB Output is correct
6 Correct 15 ms 23916 KB Output is correct
7 Correct 25 ms 24120 KB Output is correct
8 Correct 21 ms 24020 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 19 ms 23892 KB Output is correct
11 Correct 155 ms 34240 KB Output is correct
12 Correct 176 ms 35124 KB Output is correct
13 Correct 193 ms 36412 KB Output is correct
14 Correct 329 ms 39200 KB Output is correct
15 Correct 483 ms 40124 KB Output is correct
16 Correct 375 ms 45696 KB Output is correct
17 Execution timed out 3100 ms 47000 KB Time limit exceeded
18 Halted 0 ms 0 KB -