oj.uz

답안 #627132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
627132 2022-08-12T08:54:47 Z Do_you_copy One-Way Streets (CEOI17_oneway) C++17
100 / 100
 138 ms 36364 KB 
#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e5 + 1;
int n, m, k;

struct TDSU{
    vector <pii> save;
    vector <int> lab;
    TDSU(){}
    TDSU(int _n){
        lab.resize(_n, -1);
    }
    inline void resize(int _n){
        lab.resize(_n, -1);
    }
    inline int find_set(int u){
        if (lab[u] < 0) return u;
        return lab[u] = find_set(lab[u]);
    }
    inline int find(int u){
        if (lab[u] < 0) return u;
        return find(lab[u]);
    }
    inline void merge(int u, int v){
        if (lab[u] > lab[v]) swap(u, v);
        save.pb({v, lab[v]});
        lab[u] += lab[v];
        lab[v] = u;
    }
    inline void undo(){

        int v = save.back().fi;
        int u = lab[v];
        lab[v] = save.back().se;
        lab[u] -= lab[v];
        save.pop_back();
    }
    inline void clear(){
        lab.clear();
        save.clear();
    }
    inline void reset(int _n){
        clear();
        resize(_n);
    }
    inline void roll_back(int _n){
        while (save.size() > _n) undo();
    }
};
TDSU dsu;
int timedfs, low[maxN], num[maxN];
int id[maxN];
int mark[maxN];
int node_cnt;

struct TEdge{
    int u, v, idx;
};
TEdge e[maxN];
vector <TEdge> adj[maxN];

void dfs(int u, int idx){
    low[u] = num[u] = ++timedfs;
    for (auto i: adj[u]){
        int v = i.u ^ i.v ^ u;
        if (i.idx == idx) continue;
        if (!num[v]){
            dfs(v, i.idx);
            low[u] = min(low[u], low[v]);
            if (low[v] == num[v]) mark[i.idx] = 1;
        }
        else{
            low[u] = min(low[u], num[v]);
        }
    }
}

vector <pii> adj1[maxN];
int lift[maxN][20];
int depth[maxN];
int val[maxN];

void dfs1(int u, int p){
    lift[u][0] = p;
    depth[u] = depth[p] + 1;
    for (int i = 1; i < 20; ++i){
        lift[u][i] = lift[lift[u][i - 1]][i - 1];
        if (!lift[u][i]) break;
    }
    for (auto i: adj1[u]){
        int v = i.fi;
        if (v == p) continue;
        dfs1(v, u);
    }
}

int lca(int u, int v){
    if (depth[u] < depth[v]) swap(u, v);
    int k = depth[u] - depth[v];
    while (k){
        int t = k & -k;
        u = lift[u][__lg(t)];
        k -= t;
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; --i){
        if (lift[u][i] != lift[v][i]){
            u = lift[u][i];
            v = lift[v][i];
        }
    }
    return lift[u][0];
}

void dfs2(int u, int p){
    for (auto i: adj1[u]){
        int v = i.fi;
        if (v == p) continue;
        dfs2(v, u);
        val[u] += val[v];
        if (!val[v]){
            mark[abs(i.se)] = 0;
        }
        else if (val[v] * i.se < 0) mark[abs(i.se)] = 1;
        else mark[abs(i.se)] = -1;
    }
}

void Init(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        cin >> e[i].u >> e[i].v;
        e[i].idx = i;
        adj[e[i].u].pb(e[i]);
        adj[e[i].v].pb(e[i]);
    }
    for (int i = 1; i <= n; ++i){
        if (!num[i]) dfs(i, 0);
    }
    dsu.resize(n + 1);
    vector <int> bridge;
    for (int i = 1; i <= m; ++i){
        if (!mark[i]){
            int x = dsu.find_set(e[i].u);
            int y = dsu.find_set(e[i].v);
            if (x != y){
                dsu.merge(x, y);
            }
        }
        else bridge.pb(i);
    }
    for (int i = 1; i <= n; ++i){
        int j = dsu.find_set(i);
        if (!id[j]) id[j] = ++node_cnt;
        id[i] = id[j];
    }
    for (int i: bridge){
        int u = id[e[i].u];
        int v = id[e[i].v];
        adj1[u].pb({v, i});
        adj1[v].pb({u, -i});
    }
    for (int i = 1; i <= node_cnt; ++i){
        if (!lift[i][0]){
            dfs1(i, 0);
        }
    }
    cin >> k;
    for (int i = 1; i <= k; ++i){
        int u, v;
        cin >> u >> v;
        u = id[u];
        v = id[v];
        ++val[u];
        --val[v];
    }
    for (int i = 1; i <= node_cnt; ++i){
        if (!lift[i][0]){
            dfs2(i, 0);
        }
    }
    for (int i = 1; i <= m; ++i){
        int x = id[e[i].u];
        int y = id[e[i].v];
        if (x == y) cout << "B";
        if(depth[x]>depth[y]){
            if(!val[x]) cout<<"B";
            if(val[x] > 0) cout<<"R";
            if(val[x] < 0) cout<<"L";
        }
        if(depth[x] < depth[y]){
            if(!val[y]) cout<<"B";
            if(val[y] > 0) cout<<"L";
            if(val[y] < 0) cout<<"R";
        }
    }
}

#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message

oneway.cpp: In member function 'void TDSU::roll_back(int)':
oneway.cpp:72:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         while (save.size() > _n) undo();
      |                ~~~~~~~~~~~~^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:228:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 6 ms 9740 KB Output is correct
7 Correct 6 ms 9960 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9748 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 6 ms 9740 KB Output is correct
7 Correct 6 ms 9960 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9748 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 53 ms 16728 KB Output is correct
12 Correct 47 ms 18044 KB Output is correct
13 Correct 52 ms 19516 KB Output is correct
14 Correct 59 ms 22528 KB Output is correct
15 Correct 65 ms 23952 KB Output is correct
16 Correct 100 ms 29860 KB Output is correct
17 Correct 105 ms 31172 KB Output is correct
18 Correct 101 ms 29856 KB Output is correct
19 Correct 90 ms 32244 KB Output is correct
20 Correct 45 ms 17272 KB Output is correct
21 Correct 41 ms 17364 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 7 ms 9940 KB Output is correct
6 Correct 6 ms 9740 KB Output is correct
7 Correct 6 ms 9960 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9748 KB Output is correct
10 Correct 5 ms 9812 KB Output is correct
11 Correct 53 ms 16728 KB Output is correct
12 Correct 47 ms 18044 KB Output is correct
13 Correct 52 ms 19516 KB Output is correct
14 Correct 59 ms 22528 KB Output is correct
15 Correct 65 ms 23952 KB Output is correct
16 Correct 100 ms 29860 KB Output is correct
17 Correct 105 ms 31172 KB Output is correct
18 Correct 101 ms 29856 KB Output is correct
19 Correct 90 ms 32244 KB Output is correct
20 Correct 45 ms 17272 KB Output is correct
21 Correct 41 ms 17364 KB Output is correct
22 Correct 138 ms 31124 KB Output is correct
23 Correct 121 ms 31932 KB Output is correct
24 Correct 119 ms 32200 KB Output is correct
25 Correct 120 ms 36364 KB Output is correct
26 Correct 124 ms 33104 KB Output is correct
27 Correct 112 ms 32100 KB Output is correct
28 Correct 34 ms 15244 KB Output is correct
29 Correct 61 ms 19060 KB Output is correct
30 Correct 60 ms 19408 KB Output is correct
31 Correct 79 ms 19572 KB Output is correct
32 Correct 78 ms 25052 KB Output is correct