Submission #31982

#	Time	Username	Problem	Language	Result	Execution time	Memory
31982		TAMREF	Dreaming (IOI13_dreaming)	C++11	100 / 100	127 ms	15224 KiB

dreaming

#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));
    }
    return R;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ii z;
    for(int i=0;i<M;i++){
        G[A[i]].push_back({B[i],T[i]});
        G[B[i]].push_back({A[i],T[i]});
    }
    for(int i=0;i<N;i++){
        if(!vis[i]){
            pnt[i]=-1;
            s[gnum]=dfs(i).second;
            pnt[s[gnum]]=-1;
            tie(radi[gnum],t[gnum])=dfs(s[gnum]);
            U[gnum]=radius(s[gnum],t[gnum],radi[gnum]);
            ++gnum;
        }
    }
    int ans = *max_element(radi,radi+gnum);
    sort(U,U+gnum);
    for(int s=gnum;s>1;s--){
        ans=max(ans,U[s-2]+L+U[s-1]);
        U[s-2]=max(U[s-2]+L,U[s-1]);
    }
    return ans;
}

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