Submission #488450

#	Time	Username	Problem	Language	Result	Execution time	Memory
488450		SirCovidThe19th	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	157 ms	13304 KiB

oneway

#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; //cant go to descendent or use par edg
		if (!tin[nxt]){
            dfs(nxt, id); 
            active[cur] += active[nxt]; 
			actQry[cur] += actQry[nxt];
            if (!active[nxt]){ 
                int curL = (cur == l[id]) ? -1 : 1; 
                int dir = !actQry[nxt] ? 0 : (actQry[nxt] < 0 ? -1 : 1); //-1 up, 1 down
                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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40