Submission #71491

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
71491	2018-08-24 23:04:57	RezwanArefin01	Race (IOI11_race)	C++17	100 / 100	2109 ms	114532 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii; 
const int maxn = 2e5 + 10; 
vector<int> adj[maxn], cost[maxn]; 
ll dist[maxn]; bool vis[maxn]; 
int sub[maxn], len[maxn], n, k; 
int ans = 1e9; 
void calc(int u, int par) {
  sub[u] = 1;
  for(int v : adj[u]) if(v - par && !vis[v]) 
    calc(v, u), sub[u] += sub[v];
}
int centroid(int u, int par, int r) {
  for(int v : adj[u]) if(v - par && !vis[v]) 
    if(sub[v] > r) return centroid(v, u, r);
  return u;
}
vector<int> vert; int in[maxn], out[maxn];
void dfs(int u, int par) { 
  in[u] = vert.size(); vert.push_back(u);
  for(int i = 0; i < adj[u].size(); ++i) {
    int v = adj[u][i], c = cost[u][i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57