oj.uz

Submission #695074

# Submission time Handle Problem Language Result Execution time Memory
695074 2023-02-04T17:21:18 Z ShaShi One-Way Streets (CEOI17_oneway) C++17
100 / 100
 127 ms 30152 KB 
/** This is the end ... **/
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define int long long int
#define dint long double
#define endl "\n"
#define pii pair<int, int>
#define pb push_back
#define F first
#define S second

using namespace std;

const int MOD = (int)1e9 + 7;
const int MAXN = (int)2e5 + 23;
const int MAXK = (int)40000 + 23;
const int MAX_LOG = 23;
const int PRM = (int)31622 + 23;
const int INF = (int)9e9;

int POW(int x, int y) {
    return (!y ? 1 : (y & 1 ? x * POW(x * x % MOD, y / 2) % MOD : POW(x * x % MOD, y / 2) % MOD));
}

int n, m, s, q, t, tmp, tmp2, cmp, u, v, u2, v2, ans1, ans2, k, flag, l, r, mid;
int arr[MAXN], cnt[MAXN], h[MAXN], seen[MAXN], pow2dad[MAXN][MAX_LOG], cnt2[MAXN], dad[MAXN], bala[MAXN], payin[MAXN], bkedge[MAXN];
vector<pii> g[MAXN];
vector<pii> edges;
vector<int> vec, e[MAXN];

int num[MAXN], low[MAXN], ti, comp[MAXN], w[MAXN];
 
void dfs(int u, int p) {
     vec.push_back(u);
     low[u] = num[u] = ++ti;
     for (int i = 0; i < g[u].size(); ++i) {
          int v = g[u][i].first;
          int id = g[u][i].second;
          if (id == p) continue;
          if (comp[v]) continue;
          if (!num[v]) {
               dfs(v, id);
               low[u] = min(low[u], low[v]);
          } else low[u] = min(low[u], num[v]);
     }
     if (low[u] == num[u]) {
          ++m;
          while (vec.size()) {
               int v = vec.back();
               vec.pop_back();
               comp[v] = m;
               for (auto w: g[v]) {
                    if (comp[w.first] && m != comp[w.first]) e[m].push_back(comp[w.first]);
               }
               if (v == u) break;
          }
     }
}
 
void pull(int u) {
     num[u] = 1;
     for (auto v: e[u]) {
          if (!num[v]) pull(v);
          w[u] += w[v];
     }
}


int32_t main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

     cin >> n >> m;

     for (int i=1; i<=m; i++) {
          cin >> u >> v;

          edges.pb({u, v});

          g[u].pb({v, i});
          g[v].pb({u, i});
     }

     for (int i = 1; i <= n; ++i) {
          if (num[i]) continue;
          dfs(i, 0);
     }
     cin >> q;
     while (q--) {
          int u, v;
          cin >> u >> v;
          u = comp[u], v = comp[v];
          if (u == v) continue;
          ++w[u], --w[v];
     }
     memset(num, 0, sizeof(num));
     for (int i = 1; i <= m; ++i) {
          if (num[i]) continue;
          pull(i);
     }
     for (int i = 0; i < edges.size(); ++i) {
          int u = edges[i].first;
          int v = edges[i].second;
          u = comp[u], v = comp[v];
          if (u == v) {
               cout << 'B';
               continue;
          }
          if (u > v) {
               if (w[v] < 0) cout << 'R';
               if (w[v] > 0) cout << 'L';
               if (w[v] == 0) cout << 'B';
          } else {
               if (w[u] < 0) cout << 'L';
               if (w[u] > 0) cout << 'R';
               if (w[u] == 0) cout << 'B';
          }
     }




     return 0;
}

Compilation message

oneway.cpp: In function 'void dfs(long long int, long long int)':
oneway.cpp:37:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |      for (int i = 0; i < g[u].size(); ++i) {
      |                      ~~^~~~~~~~~~~~~
oneway.cpp: In function 'int32_t main()':
oneway.cpp:101:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |      for (int i = 0; i < edges.size(); ++i) {
      |                      ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 8 ms 11220 KB Output is correct
3 Correct 7 ms 11348 KB Output is correct
4 Correct 7 ms 11348 KB Output is correct
5 Correct 8 ms 11348 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct
7 Correct 8 ms 11416 KB Output is correct
8 Correct 8 ms 11396 KB Output is correct
9 Correct 6 ms 11348 KB Output is correct
10 Correct 7 ms 11404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 8 ms 11220 KB Output is correct
3 Correct 7 ms 11348 KB Output is correct
4 Correct 7 ms 11348 KB Output is correct
5 Correct 8 ms 11348 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct
7 Correct 8 ms 11416 KB Output is correct
8 Correct 8 ms 11396 KB Output is correct
9 Correct 6 ms 11348 KB Output is correct
10 Correct 7 ms 11404 KB Output is correct
11 Correct 51 ms 20936 KB Output is correct
12 Correct 54 ms 21948 KB Output is correct
13 Correct 74 ms 23356 KB Output is correct
14 Correct 77 ms 24060 KB Output is correct
15 Correct 90 ms 24160 KB Output is correct
16 Correct 99 ms 23444 KB Output is correct
17 Correct 72 ms 25504 KB Output is correct
18 Correct 67 ms 23384 KB Output is correct
19 Correct 72 ms 26832 KB Output is correct
20 Correct 71 ms 21712 KB Output is correct
21 Correct 54 ms 21252 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 8 ms 11220 KB Output is correct
3 Correct 7 ms 11348 KB Output is correct
4 Correct 7 ms 11348 KB Output is correct
5 Correct 8 ms 11348 KB Output is correct
6 Correct 6 ms 11348 KB Output is correct
7 Correct 8 ms 11416 KB Output is correct
8 Correct 8 ms 11396 KB Output is correct
9 Correct 6 ms 11348 KB Output is correct
10 Correct 7 ms 11404 KB Output is correct
11 Correct 51 ms 20936 KB Output is correct
12 Correct 54 ms 21948 KB Output is correct
13 Correct 74 ms 23356 KB Output is correct
14 Correct 77 ms 24060 KB Output is correct
15 Correct 90 ms 24160 KB Output is correct
16 Correct 99 ms 23444 KB Output is correct
17 Correct 72 ms 25504 KB Output is correct
18 Correct 67 ms 23384 KB Output is correct
19 Correct 72 ms 26832 KB Output is correct
20 Correct 71 ms 21712 KB Output is correct
21 Correct 54 ms 21252 KB Output is correct
22 Correct 85 ms 26760 KB Output is correct
23 Correct 86 ms 24912 KB Output is correct
24 Correct 91 ms 24640 KB Output is correct
25 Correct 89 ms 30152 KB Output is correct
26 Correct 95 ms 26180 KB Output is correct
27 Correct 127 ms 24952 KB Output is correct
28 Correct 60 ms 18248 KB Output is correct
29 Correct 77 ms 22036 KB Output is correct
30 Correct 91 ms 22476 KB Output is correct
31 Correct 99 ms 22900 KB Output is correct
32 Correct 78 ms 25400 KB Output is correct