Submission #488449

#TimeUsernameProblemLanguageResultExecution timeMemory
488449SirCovidThe19thOne-Way Streets (CEOI17_oneway)C++17
100 / 100
129 ms15612 KiB
#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 (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++){
      |                  ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...