Submission #128762

#	Time	Username	Problem	Language	Result	Execution time	Memory
128762		LittleFlowers__	꿈 (IOI13_dreaming)	C++14	100 / 100	163 ms	23256 KiB

dreaming

#include"dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "TASK"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))

const int SZ=100010;

int fre[SZ],g[SZ];
vector<int> node;
vector<ii> f[SZ],ad[SZ];

void dfs1(int u,int p=-1){
    fre[u]++;
    f[u].resize(3);
    forv(v,ad[u]) if(v.fi!=p){
        dfs1(v.fi,u);
        f[u][2]={f[v.fi][0].fi+v.se,v.fi};
        fordec(i,1,0) if(f[u][i]<f[u][i+1]) swap(f[u][i],f[u][i+1]);
    }
}
void dfs2(int u,int p=-1){
    node.pb(u); fre[u]++;
    forv(v,ad[u]) if(v.fi!=p){
        g[v.fi]=max(g[u],f[u][f[u][0].se==v.fi].fi)+v.se;
        dfs2(v.fi,u);
    }
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    forinc(i,0,N-1) ad[i].clear();
    forinc(i,0,M-1){
        ad[A[i]].pb({B[i],T[i]});
        ad[B[i]].pb({A[i],T[i]});
    }
    forinc(i,0,N-1) if(!fre[i])  dfs1(i);
    vector<int> h;
    forinc(i,0,N-1) if(fre[i]<2){
        node.clear();
        dfs2(i);
        int tmp=1<<29;
        forv(j,node) tmp=min(tmp,max(f[j][0].fi,g[j]));
        h.pb(tmp);
    }
    int ret=0;
    forinc(i,0,N-1) ret=max(ret,f[i][0].fi+g[i]);
    sort(all(h),greater<int>());
    forinc(i,1,h.size()-1){
        ret=max(ret,h[i]+h[i-1]+L);
        h[i]=min(max(h[i-1]+L,h[i]),max(h[i-1],h[i]+L));
    }
    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