Submission #31982

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
31982	2017-09-20 10:54:24	TAMREF	Dreaming (IOI13_dreaming)	C++11	100 / 100	127 ms	15224 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;
#define va first
#define vb second
typedef pair<int,int> ii;
const int mx = 100005;
vector<ii> G[mx];
int gnum;
int vis[mx], s[mx], t[mx], pnt[mx], fd[mx], des[mx], radi[mx], U[mx], pc[mx];
ii dfs(int x){
    vis[x]=1; des[x]=x;
    ii z(0,x), w;
    for(ii &u : G[x]){
        if(u.va == pnt[x]) continue;
        pnt[u.va]=x;  pc[u.va]=u.vb;
        w=dfs(u.va); w={w.va+u.vb,w.vb};
        if(z<w){
            z=w;
            des[x]=u.va;
        }
    }
    fd[x]=z.vb;
    return z;
}
static int radius(int s, int t, int r){
    int R=r, S=0;
    for(int now=des[s];S<r;now=des[now]){
        S+=pc[now];
        R=min(R,max(S,r-S));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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