oj.uz

Submission #488449

# Submission time Handle Problem Language Result Execution time Memory
488449 2021-11-19T00:43:17 Z SirCovidThe19th One-Way Streets (CEOI17_oneway) C++17
100 / 100
 129 ms 15612 KB 
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 5;

int n, m, q, l[mx], r[mx], tin[mx], ti, in[mx], active[mx], actQry[mx], ans[mx]; 
vector<pair<int, int>> adj[mx]; 

void dfs(int cur, int pedge){
    tin[cur] = ++ti;
	for (int i = 0; i < adj[cur].size(); i++){
		int nxt, id; tie(nxt, id) = adj[cur][i];
		if (id == pedge or tin[nxt] > tin[cur]) continue;
		if (!tin[nxt]){
            dfs(nxt, id); 
            active[cur] += active[nxt]; 
			actQry[cur] += actQry[nxt];
            if (!active[nxt]){
                int curL = (cur == l[id]) ? -1 : 1, dir = 0; 
				if (actQry[nxt] < 0) dir = -1;
				if (actQry[nxt] > 0) dir = 1;
                ans[id] = curL * dir;
            }
        }
        else in[nxt]++, active[cur]++;
	}
    active[cur] -= in[cur];
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int a, b; cin >> a >> b; 
        l[i] = a; r[i] = b;
        adj[a].push_back({b, i}); adj[b].push_back({a, i});
    }
    cin >> q;
    for (int i = 1; i <= q; i++){
        int a, b; cin >> a >> b;
        actQry[a]++; actQry[b]--;
    }
    for (int i = 1; i <= n; i++) if (!tin[i]) dfs(i, 0);
    for (int i = 1; i <= m; i++) cout<<(!ans[i] ? "B" : (ans[i] == -1 ? "L" : "R"));
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (int i = 0; i < adj[cur].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 2 ms 2660 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 2 ms 2660 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 62 ms 8784 KB Output is correct
12 Correct 70 ms 10084 KB Output is correct
13 Correct 78 ms 11280 KB Output is correct
14 Correct 90 ms 12000 KB Output is correct
15 Correct 85 ms 12148 KB Output is correct
16 Correct 84 ms 9928 KB Output is correct
17 Correct 78 ms 11424 KB Output is correct
18 Correct 82 ms 9956 KB Output is correct
19 Correct 74 ms 12632 KB Output is correct
20 Correct 72 ms 9464 KB Output is correct
21 Correct 66 ms 9520 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct
3 Correct 2 ms 2768 KB Output is correct
4 Correct 2 ms 2660 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 2 ms 2768 KB Output is correct
7 Correct 2 ms 2768 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 62 ms 8784 KB Output is correct
12 Correct 70 ms 10084 KB Output is correct
13 Correct 78 ms 11280 KB Output is correct
14 Correct 90 ms 12000 KB Output is correct
15 Correct 85 ms 12148 KB Output is correct
16 Correct 84 ms 9928 KB Output is correct
17 Correct 78 ms 11424 KB Output is correct
18 Correct 82 ms 9956 KB Output is correct
19 Correct 74 ms 12632 KB Output is correct
20 Correct 72 ms 9464 KB Output is correct
21 Correct 66 ms 9520 KB Output is correct
22 Correct 124 ms 12616 KB Output is correct
23 Correct 125 ms 10976 KB Output is correct
24 Correct 129 ms 11064 KB Output is correct
25 Correct 122 ms 15612 KB Output is correct
26 Correct 121 ms 12212 KB Output is correct
27 Correct 120 ms 11080 KB Output is correct
28 Correct 70 ms 6696 KB Output is correct
29 Correct 120 ms 10196 KB Output is correct
30 Correct 115 ms 10584 KB Output is correct
31 Correct 118 ms 10580 KB Output is correct
32 Correct 115 ms 12980 KB Output is correct