oj.uz

Submission #695082

# Submission time Handle Problem Language Result Execution time Memory
695082 2023-02-04T17:24:47 Z ShaShi One-Way Streets (CEOI17_oneway) C++17
100 / 100
 154 ms 27880 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> adj[MAXN];
vector<pii> edges;
vector<int> vec, e[MAXN];

int low[MAXN], ti, comp[MAXN], w[MAXN];
 
void dfs(int u, int p) {
     vec.pb(u);
     low[u] = seen[u] = ++ti;
     for (int i = 0; i < adj[u].size(); ++i) {
          int v = adj[u][i].first;
          int id = adj[u][i].second;
          if (id == p) continue;
          if (comp[v]) continue;
          if (!seen[v]) {
               dfs(v, id);
               low[u] = min(low[u], low[v]);
          } else low[u] = min(low[u], seen[v]);
     }
     if (low[u] == seen[u]) {
          ++m;
          while (vec.size()) {
               int v = vec.back();
               vec.pop_back();
               comp[v] = m;
               for (auto w: adj[v]) {
                    if (comp[w.first] && m != comp[w.first]) e[m].pb(comp[w.first]);
               }
               if (v == u) break;
          }
     }
}
 
void DFS2(int u) {
     seen[u] = 1;
     for (auto v: e[u]) {
          if (!seen[v]) DFS2(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});

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

     for (int i = 1; i <= n; ++i) {
          if (!seen[i]) 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];
     }

     fill(seen, seen+m+1, 0);
     for (int i = 1; i <= m; ++i) {
          if (!seen[i]) DFS2(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 < adj[u].size(); ++i) {
      |                      ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'int32_t main()':
oneway.cpp:103: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]
  103 |      for (int i = 0; i < edges.size(); ++i) {
      |                      ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 8 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9776 KB Output is correct
7 Correct 6 ms 9920 KB Output is correct
8 Correct 6 ms 9888 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 8 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9776 KB Output is correct
7 Correct 6 ms 9920 KB Output is correct
8 Correct 6 ms 9888 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct
11 Correct 41 ms 19020 KB Output is correct
12 Correct 60 ms 20148 KB Output is correct
13 Correct 59 ms 21388 KB Output is correct
14 Correct 99 ms 22328 KB Output is correct
15 Correct 154 ms 22564 KB Output is correct
16 Correct 85 ms 22300 KB Output is correct
17 Correct 100 ms 24392 KB Output is correct
18 Correct 69 ms 22280 KB Output is correct
19 Correct 71 ms 25680 KB Output is correct
20 Correct 48 ms 19740 KB Output is correct
21 Correct 45 ms 19360 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 8 ms 9812 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 8 ms 9776 KB Output is correct
7 Correct 6 ms 9920 KB Output is correct
8 Correct 6 ms 9888 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct
11 Correct 41 ms 19020 KB Output is correct
12 Correct 60 ms 20148 KB Output is correct
13 Correct 59 ms 21388 KB Output is correct
14 Correct 99 ms 22328 KB Output is correct
15 Correct 154 ms 22564 KB Output is correct
16 Correct 85 ms 22300 KB Output is correct
17 Correct 100 ms 24392 KB Output is correct
18 Correct 69 ms 22280 KB Output is correct
19 Correct 71 ms 25680 KB Output is correct
20 Correct 48 ms 19740 KB Output is correct
21 Correct 45 ms 19360 KB Output is correct
22 Correct 93 ms 24428 KB Output is correct
23 Correct 81 ms 22544 KB Output is correct
24 Correct 107 ms 22240 KB Output is correct
25 Correct 92 ms 27880 KB Output is correct
26 Correct 87 ms 23864 KB Output is correct
27 Correct 99 ms 22596 KB Output is correct
28 Correct 41 ms 16312 KB Output is correct
29 Correct 87 ms 19000 KB Output is correct
30 Correct 60 ms 19404 KB Output is correct
31 Correct 85 ms 19836 KB Output is correct
32 Correct 81 ms 22596 KB Output is correct