Submission #444007

#	Time	Username	Problem	Language	Result	Execution time	Memory
444007		Supersonic	Dreaming (IOI13_dreaming)	C++14	100 / 100	111 ms	14788 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> g[100001];int c[100001];int cc=1;int ld[100001];int rd[100001];
int cf=-1,cd=-1;int u[100001];
void mc(int i){
    //cerr<<i<<endl;
    c[i]=cc;
    for(auto j:g[i])if(c[j.first]==0)mc(j.first);
}
void ffd(int i,int d){
    if(d>cd){cd=d;cf=i;}
    u[i]=1;
    for(auto j:g[i])if(!u[j.first])ffd(j.first,d+j.second);
    u[i]=0;
}
int ff(int i){
    cf=cd=-1;
    ffd(i,0);
    return cf;
}
void fl(int i,int d){
    //cerr<<"L "<<i<<' '<<d<<endl;
    ld[i]=d;
    for(auto j:g[i])if(ld[j.first]==-1)fl(j.first,d+j.second);
}
void fr(int i,int d){
    //cerr<<"R "<<i<<' '<<d<<endl;
    rd[i]=d;
    for(auto j:g[i])if(rd[j.first]==-1)fr(j.first,d+j.second);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    //cerr<<n<<' '<<m<<endl;
    //cerr<<"A"<<endl;
    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]});}
    //cerr<<n<<' '<<m<<endl;
    for(int i=0;i<n;i++)if(!c[i]){mc(i);cc++;}
    cc--;//cerr<<cc<<endl;
    //for(int i=0;i<n;i++)cerr<<c[i]<<' ';cerr<<endl;
    int cr=1;
    for(int i=0;i<n;i++)ld[i]=rd[i]=-1;
    for(int i=0;i<n;i++){
        if(c[i]!=cr)continue;
        if(cr>cc)break;
        int l=ff(i);int r=ff(l);
        fl(l,0);fr(r,0);
        cr++;
    }
    vector<int> s={-100000000};for(int i=1;i<=cc;i++)s.push_back(1e9+1);
    for(int i=0;i<n;i++)s[c[i]]=min(s[c[i]],max(ld[i],rd[i]));
    int d[cc+1];for(int i=1;i<=cc;i++)d[i]=1e9+1;
    for(int i=0;i<n;i++)d[c[i]]=min(d[c[i]],ld[i]+rd[i]);
    int y=-1;for(int i=1;i<=cc;i++)y=max(y,d[i]);
    //for(int i=0;i<n;i++)cerr<<ld[i]+rd[i]<<endl;
    sort(s.begin(),s.end());//for(int i=1;i<=cc;i++)cout<<s[i]<<' ';cout<<endl;
    if(cc==1)return max(y,s[1]);
    //cerr<<y<<endl;
    return max({y,s[cc]+s[cc-1]+L,s[cc-1]+s[cc-2]+2*L});
}

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