Submission #319860

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
319860	2020-11-06 15:31:05	nandonathaniel	Race (IOI11_race)	C++14	100 / 100	577 ms	100452 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;
#define fi first
#define se second
const int MAXN=200005;
typedef pair<int,int> pii;
long long pref[MAXN];
vector<pii> adj[MAXN];
int depth[MAXN],KK,ans=1e9;
map<long long,int> subtree[MAXN];
void merge(int now,int nxt){
  for(map<long long,int>::iterator it=subtree[nxt].begin();it!=subtree[nxt].end();++it){
    if(subtree[now].count(it->first))subtree[now][it->first]=min(subtree[now][it->first],it->second);
    else subtree[now][it->first]=it->second;
  }
}
void dfs(int now,int par){
  subtree[now][pref[now]]=depth[now];
  //hitung semua pasangan node yang LCAnya now
  for(auto nxt : adj[now]){
    if(nxt.fi==par)continue;
    depth[nxt.fi]=depth[now]+1;
    pref[nxt.fi]=pref[now]+nxt.se;
    dfs(nxt.fi,now);
    if(subtree[now].size()<subtree[nxt.fi].size())subtree[now].swap(subtree[nxt.fi]);
  }
  for(auto nxt : adj[now]){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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