Submission #31788

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
31788	2017-09-09 03:32:36	Diuven	Dreaming (IOI13_dreaming)	C++11	100 / 100	205 ms	15964 KiB

dreaming

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 "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef struct {int to, cost;} edge;
vector<edge> G[100010], T(100010);
vector<int> rad;
bool done[100010];
int N, M, L, tmp, sz[100010], u, D;
int find(int v, bool trace=false, int p=-1, int d=0){
  done[v]=true;
  if(tmp<d) tmp=d, u=v;
  int mx=0;
  for(auto& e:G[v]){
    if(e.to==p) continue;
    int down=find(e.to, false, v, d+e.cost)+e.cost;
    if(down>mx) mx=down, T[v]=e;
  }
  return mx;
}
int findcen(int v){
  tmp=-1, find(v); int a=u;
  tmp=-1, T.clear(), find(a,true); int b=u, dia=tmp, now=0;
  while(a!=b){
    int nxt=now+T[a].cost;
    if(nxt<=dia-nxt){
      a=T[a].to, now=nxt; continue;
    }
    if(max(now, dia-now)>max(nxt, dia-nxt))
      a=T[a].to;
    break;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23