Submission #27662

#	Time	Username	Problem	Language	Result	Execution time	Memory
27662		repeating	Dreaming (IOI13_dreaming)	C++11	100 / 100	136 ms	17308 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()

using namespace std;
const long long INF = 1e9;
const int MX=100005;

int n,m,l,dis[MX],go[MX];
vector<pii> adj[MX];
bool vis[MX];
pii DFS(int ver,int par,bool b){
    vis[ver]=1;
    pii ret;
    ret={0,ver};
    pii p;
    for(auto i : adj[ver]){
        if(i.F==par)C;
        if(b)dis[i.F]=dis[ver]+i.S;
        p=DFS(i.F,ver,b);
        p.F+=i.S;
        if(p.F>=ret.F){
            ret.F=p.F;
            ret.S=p.S;
        }
    }
//    cout<<ver<<" "<<ret.F<<" "<<ret.S<<endl;
    if(b)go[ver]=ret.F;
    R ret;
}
pii dfs(int ver,int dia,int par){
    if(dis[ver]+go[ver]!=dia)R {0,INF};
    pii ret={dis[ver],go[ver]};
//    cout<<ver<<" "<<dis[ver]<<" "<<go[ver]<<endl;
    for(auto i : adj[ver]){
        if(par==i.F)C;
        pii p=dfs(i.F,dia,ver);
        if(abs(p.F-p.S)<abs(ret.F-ret.S)){
            ret=p;
        }
    }
    R ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N,m=M,l=L;
    for(int i=0;i<m;i++){
        adj[A[i]].pb({B[i],T[i]});
        adj[B[i]].pb({A[i],T[i]});
    }
    int mx1=0,mx2=0;
    int ret=0;
    vector<int>v;
    for(int i=0;i<n;i++){
        if(vis[i])C;
        pii p=DFS(i,-1,0);
        int x=p.S;
        p=DFS(p.S,-1,1);
        pii d=dfs(x,p.F,-1);
        ret=max(ret,p.F);
//        cout<<i<<" "<<p.F<<" "<<d.F<<" "<<d.S<<endl;
        if(d.F<d.S)swap(d.F,d.S);
        mx2=max(mx2,d.F);
        v.pb(d.F);
        if(mx1<mx2)swap(mx1,mx2);
    }
    sort(all(v));
    reverse(all(v));
    int b=N-M-1;
    if(b>1){
        ret=max(ret,2*L);
        ret=max(ret,v[1]+v[2]+l+l);
    }
    ret=max(ret,mx1+mx2+(l*(b>0)));
    return ret;
}

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