oj.uz

Submission #627110

# Submission time Handle Problem Language Result Execution time Memory
627110 2022-08-12T08:02:49 Z Do_you_copy One-Way Streets (CEOI17_oneway) C++17
60 / 100
 103 ms 28732 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 = 1e5 + 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);
                //cerr << e[i].u << " " << e[i].v << "?\n";
            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){
        if (!mark[i]) cout << 'B';
        else if (mark[i] < 0) cout << 'L';
        else 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:220:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 37 ms 12976 KB Output is correct
12 Correct 42 ms 14484 KB Output is correct
13 Correct 50 ms 15952 KB Output is correct
14 Correct 65 ms 18940 KB Output is correct
15 Correct 71 ms 20460 KB Output is correct
16 Correct 83 ms 26328 KB Output is correct
17 Correct 87 ms 27600 KB Output is correct
18 Correct 91 ms 26352 KB Output is correct
19 Correct 91 ms 28732 KB Output is correct
20 Correct 47 ms 13676 KB Output is correct
21 Correct 46 ms 13732 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 37 ms 12976 KB Output is correct
12 Correct 42 ms 14484 KB Output is correct
13 Correct 50 ms 15952 KB Output is correct
14 Correct 65 ms 18940 KB Output is correct
15 Correct 71 ms 20460 KB Output is correct
16 Correct 83 ms 26328 KB Output is correct
17 Correct 87 ms 27600 KB Output is correct
18 Correct 91 ms 26352 KB Output is correct
19 Correct 91 ms 28732 KB Output is correct
20 Correct 47 ms 13676 KB Output is correct
21 Correct 46 ms 13732 KB Output is correct
22 Incorrect 103 ms 28716 KB Output isn't correct
23 Halted 0 ms 0 KB -