Submission #797773

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
797773	2023-07-29 21:34:44	ttamx	Race (IOI11_race)	C++14	100 / 100	221 ms	35084 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 "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p2;
const int N=2e5+5;
const int K=1e6+5;
int n,k;
int ans;
vector<p2> adj[N];
int sz[N];
bool used[N];
int dist[K];
vector<int> res;
vector<p2> res2;
int dfssz(int u,int p=-1){
  sz[u]=1;
  for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=dfssz(v,u);
  return sz[u];
}
int centroid(int u,int cnt,int p=-1){
  for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]*2>cnt)return centroid(v,cnt,u);
  return u;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

race.cpp: In function 'int dfssz(int, int)':
race.cpp:22:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |  for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=dfssz(v,u);
      |           ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:27:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]*2>cnt)return centroid(v,cnt,u);
      |           ^
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:36:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |  for(auto [v,w]:adj[u])if(v!=p&&!used[v])dfs(v,d+w,cnt+1,u);
      |           ^
race.cpp: In function 'void decom(int)':
race.cpp:42:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |  for(auto [v,w]:adj[u]){
      |           ^
race.cpp:45:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for(auto [x,y]:res2)dist[x]=min(dist[x],y);
      |            ^
race.cpp:50:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |  for(auto [v,w]:adj[u])if(!used[v])decom(v);
      |           ^

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