Submission #1082675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082675		boyliguanhan	Dreaming (IOI13_dreaming)	C++17	100 / 100	92 ms	32284 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[100100];
bitset<100100> vis,vis2;
int mxd[100100], MX, MN;
vector<int> lens;
void dfs1(int n){
    vis[n]=1;
    for(auto [i,j]:adj[n])if(!vis[i])
        dfs1(i), mxd[n]=max(mxd[n],mxd[i]+j);
}
void dfs2(int n,int fromp){
    vis2[n]=1,MX=max(MX,fromp);
    MN=min(MN,max(fromp,mxd[n]));
    vector<int>pre,suf;
    for(auto[i,j]:adj[n])if(!vis2[i])
        pre.push_back(mxd[i]+j),
        suf.push_back(mxd[i]+j);
    pre.insert(pre.begin(),0);
    suf.push_back(0);
    for(int i=1;i<pre.size();i++)
        pre[i]=max(pre[i],pre[i-1]);
    for(int j=pre.size()-1;j--;)
        suf[j]=max(suf[j],suf[j+1]);
    int CC=0;
    for(auto[i,j]:adj[n])if(!vis2[i]) CC++,
        dfs2(i,max({fromp,pre[CC-1],suf[CC]})+j);
}
void solve(int n){
    for(int i=0;i<n;i++)
        if(!vis[i]) MN=1e9,dfs1(i),
            dfs2(i,0),lens.push_back(MN);
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0;i<M;i++)
        adj[A[i]].push_back({B[i],T[i]}),
        adj[B[i]].push_back({A[i],T[i]});
    solve(N);
    sort(lens.rbegin(),lens.rend());
    if(lens.size()==1)
        return MX;
    else if(lens.size()==2)
        return max(MX,lens[0]+lens[1]+L);
    else return max(MX,lens[1]+L+max(lens[0],lens[2]+L));
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=1;i<pre.size();i++)
      |                 ~^~~~~~~~~~~

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