oj.uz

Submission #528194

# Submission time Handle Problem Language Result Execution time Memory
528194 2022-02-19T16:48:22 Z cig32 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 77788 KB 
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN], low[MAXN], vis[MAXN], tim = 0;
map<pair<int, int>, bool> is_bridge;
map<pair<int, int>, int> o; // appear count
void dfs(int node, int prv) {
  tin[node] = ++tim;
  int mi = 1e9;
  vis[node] = 1;
  for(int x: adj[node]) {
    if(!vis[x]) {
      dfs(x, node);
      mi = min(mi, low[x]);
      //cout << "tree edge: " << node << " -> " << x << "\n";
      if(low[x] > tin[node] && o[{x, node}] == 1) {
        //cout << "bridge found: " << x << " " << node << "\n";
        is_bridge[{x, node}] = is_bridge[{node, x}] = 1;
      }
    }
  }
  tout[node] = ++tim;
  //Calculating low[node]
  low[node] = tin[node];
  for(int x: adj[node]) {
    if(tin[x] < tin[node] && tout[x] == 0 && tin[x] > 0 && x != prv) {
      //cout << x << " is an ancestor of " << node << "\n";
      low[node] = min(low[node], tin[x]);
    }
  }
  low[node] = min(low[node], mi);
  //cout << node << ": " << tin[node] << " " << tout[node] << " " << low[node] <<" \n";
}
int dsu[MAXN];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}
vector<int> adj2[MAXN];
map<pair<int, int>, int> ord;
map<pair<int, int>, int> rel;
bool dfs2(int node, int prv, int tar) {
  bool good = (node == tar);
  if(!good) {
    for(int x: adj2[node]) {
      if(x != prv) {
        if(dfs2(x, node, tar)) {
          good = 1;
        }
      }
    }
  }
  if(good) rel[{prv, node}] = rel[{node, prv}] = prv;
  return good;
}
void solve(int tc) {
  int n, m;
  cin >> n >> m;
  for(int i=1; i<=n; i++) {
    dsu[i] = i;
  }
  pair<int, int> edges[m+1];
  for(int i=1; i<=m; i++) {
    int a, b;
    cin >> a >> b;
    edges[i] = {a, b};
    o[{a, b}]++; o[{b, a}]++;
    if(a == b) continue;
    if(o[{a, b}] > 1) continue;
    ord[edges[i]] = a;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for(int i=1; i<=n; i++) {
    if(!vis[i]) dfs(i, -1);
  }
  for(int i=1; i<=n; i++) {
    for(int x: adj[i]) {
      if(!is_bridge[{i, x}] || o[{i, x}] > 1) {
        if(set_of(i) != set_of(x)) {
          union_(i, x);
        }
      }
    }
  }
  map<pair<int, int>, bool> alr;
  for(int i=1; i<=n; i++) {
    for(int x: adj[i]) {
      if(set_of(i) != set_of(x) && !alr[{set_of(i), set_of(x)}]) {
        alr[{set_of(i), set_of(x)}] = alr[{set_of(x), set_of(i)}] = 1;
        adj2[set_of(i)].push_back(set_of(x));
        adj2[set_of(x)].push_back(set_of(i));
      }
    }
  }
  //adj2 is the bridge-block tree of the graph
  int p; cin >> p;
  for(int i=0; i<p; i++) {
    int x, y;
    cin >> x >> y;
    x = set_of(x), y = set_of(y);
    if(x == y) continue;
    dfs2(x, -1, y);
  }
  for(int i=1; i<=m; i++) {
    if(edges[i].first == edges[i].second) {
      cout << "B"; continue;
    }
    else if(o[edges[i]] > 1) {
      cout << "B"; continue;
    }
    else if(!is_bridge[edges[i]]) {
      cout << "B"; continue;
    }
    int r = rel[{set_of(edges[i].first), set_of(edges[i].second)}];
    int q = set_of(ord[edges[i]]);
    if(r > 0) cout << (r == q ? "R" : "L");
    else cout << "B";
  }
  cout << "\n";
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1;// cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}  
/*
12 11
1 2
1 2
4 3
2 3
1 3
5 1
4 6
6 4
9 10
10 11
11 12
3
9 12
12 9
5 6

i thought you said you were busy? ._.

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 5 ms 5452 KB Output is correct
4 Correct 6 ms 5580 KB Output is correct
5 Correct 10 ms 5708 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 10 ms 5764 KB Output is correct
8 Correct 7 ms 5600 KB Output is correct
9 Correct 5 ms 5352 KB Output is correct
10 Correct 5 ms 5292 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 5 ms 5452 KB Output is correct
4 Correct 6 ms 5580 KB Output is correct
5 Correct 10 ms 5708 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 10 ms 5764 KB Output is correct
8 Correct 7 ms 5600 KB Output is correct
9 Correct 5 ms 5352 KB Output is correct
10 Correct 5 ms 5292 KB Output is correct
11 Correct 485 ms 45344 KB Output is correct
12 Correct 547 ms 47216 KB Output is correct
13 Correct 539 ms 50104 KB Output is correct
14 Correct 601 ms 55256 KB Output is correct
15 Correct 743 ms 57256 KB Output is correct
16 Correct 1091 ms 69460 KB Output is correct
17 Correct 2950 ms 76508 KB Output is correct
18 Correct 1947 ms 69536 KB Output is correct
19 Correct 2808 ms 77788 KB Output is correct
20 Correct 487 ms 46700 KB Output is correct
21 Correct 343 ms 44740 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 5 ms 5452 KB Output is correct
4 Correct 6 ms 5580 KB Output is correct
5 Correct 10 ms 5708 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 10 ms 5764 KB Output is correct
8 Correct 7 ms 5600 KB Output is correct
9 Correct 5 ms 5352 KB Output is correct
10 Correct 5 ms 5292 KB Output is correct
11 Correct 485 ms 45344 KB Output is correct
12 Correct 547 ms 47216 KB Output is correct
13 Correct 539 ms 50104 KB Output is correct
14 Correct 601 ms 55256 KB Output is correct
15 Correct 743 ms 57256 KB Output is correct
16 Correct 1091 ms 69460 KB Output is correct
17 Correct 2950 ms 76508 KB Output is correct
18 Correct 1947 ms 69536 KB Output is correct
19 Correct 2808 ms 77788 KB Output is correct
20 Correct 487 ms 46700 KB Output is correct
21 Correct 343 ms 44740 KB Output is correct
22 Execution timed out 3060 ms 72812 KB Time limit exceeded
23 Halted 0 ms 0 KB -