Submission #196851

#	Time	Username	Problem	Language	Result	Execution time	Memory
196851		awlintqaa	Dreaming (IOI13_dreaming)	C++14	18 / 100	535 ms	28608 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ppb pop_back
#define C continue
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<pi> vpi;
#include "dreaming.h"
ll n,m,k;
vpll v[100009];
map<pll,ll>mp;
ll done[100009];
vll ret;
vpll all;
ll mx,id,z;
void dfs1(int node,int p,ll crnt){
        done[node]=1;
        if(crnt>=mx){
                mx=crnt;
                id=node;
        }
        for(auto u:v[node]){
                if(u.fi==p)C;
                dfs1(u.fi,node,crnt+u.se);
        }
}
void dfs2(int node,int p){
        done[node]=1;
        if(!z)ret.pb(node);
        if(node==id){
                z=1;
                return ;
        }
        for(auto u:v[node]){
                if(u.fi==p)C;
                dfs2(u.fi,node);
                if(z)return ;
        }
        if(!z)ret.ppb();
}
pll find(){
        vll X;
        X.resize((int)ret.size());
        ll crnt=0;
        for(int i=0;i<ret.size();i++){
                if(i)crnt+=mp[{ret[i],ret[i-1]}];
                X[i]=max(X[i],crnt);
        }
        crnt=0;
        ll timer=ret.size()-1;
        for(int i=0;i<ret.size();i++){
                if(i)crnt+=mp[{ret[i],ret[i-1]}];
                X[timer]=max(X[timer],crnt);
                timer--;
        }
        ll mn=1e9*2,id=0;
        for(int i=0;i<X.size();i++){
                if(X[i]<mn){
                        mn=X[i];
                        id=i;
                }
        }
        reverse(ret.begin(),ret.end());
        return {mn,ret[id]};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
        n=N,m=M,k=L;
        for(int i=0;i<m;i++){
                int a=A[i],b=B[i],c=T[i];
                v[a].pb({b,c});
                v[b].pb({a,c});
                mp[{a,b}]=mp[{b,a}]=c;
        }
        for(int i=0;i<n;i++){
                if(done[i])C;
                mx=id=-1;
                z=0;
                ret.clear();
                dfs1(i,i,0);
                int xxx=id;
                mx=id=-1;
                dfs1(xxx,xxx,0);
                dfs2(xxx,xxx);
                all.pb(find());
        }
        sort(all.begin(),all.end());
        reverse(all.begin(),all.end());
        for(int i=1;i<all.size();i++){
                int a=all[i].se,b=all[0].se,c=L;
                v[a].pb({b,c});
                v[b].pb({a,c});
        }
        mx=id=-1;
        dfs1(0,0,0);
        mx=0;
        dfs1(id,id,0);
        return mx;
}

Compilation message (stderr)

dreaming.cpp: In function 'pll find()':
dreaming.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<ret.size();i++){
                     ~^~~~~~~~~~~
dreaming.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<ret.size();i++){
                     ~^~~~~~~~~~~
dreaming.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<X.size();i++){
                     ~^~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=1;i<all.size();i++){
                     ~^~~~~~~~~~~

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