Submission #940463

#	Time	Username	Problem	Language	Result	Execution time	Memory
940463		vjudge1	Dreaming (IOI13_dreaming)	C++17	100 / 100	120 ms	25840 KiB

dreaming

#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;
vector<pair<int,int>>g[100005];
bool was[100005];
bool wass[100005];
int dd[100005];
int cost[100005];
int mn,mni;
vector<int>t;
void dfs(int v){
    wass[v]=1;
    t.push_back(v);
    for(auto u:g[v]){
        if(!wass[u.first]){
            dfs(u.first);
        }
    }
    // cout<<d[v]<<' '<<sum<<endl;
}
int mxx=0,mxi=0;
int dfss(int v,int d=0){
    was[v]=1;
    if(d>mxx){
        mxx=d;
        mxi=v;
    }
    int mx=d;
    for(auto u:g[v]){
        if(!was[u.first]){
            mx=max(mx,dfss(u.first,d+u.second));
        }
    }
    was[v]=0;
    return mx;
}
void dfsss(int v,int d=0){
    was[v]=1;
    dd[v]=0;
    int mx=d;
    for(auto u:g[v]){
        if(!was[u.first]){
            dfsss(u.first);
            dd[v]=max(dd[v],dd[u.first]+u.second);
        }
    }
    was[v]=0;
}
void dfsc(int v,int mx){
    was[v]=1;
    cost[v]=mx;
    multiset<int>s;
    for(auto u:g[v]){
        if(!was[u.first]){
            s.insert(dd[u.first]+u.second);
        }
    }
    for(auto u:g[v]){
        if(!was[u.first]){
            s.erase(s.find(dd[u.first]+u.second));
            if(!s.empty()){
                dfsc(u.first,max(mx+u.second,*s.rbegin()+u.second));
            }else{
                dfsc(u.first,mx+u.second);
            }
            s.insert(dd[u.first]+u.second);
        }
    }
    was[v]=0;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    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]});
    }
    vector<pair<int,int>>rots;
    for(int i=0;i<N;i++){
        if(!wass[i]){
            t.clear();
            mn=INT_MAX;
            dfs(i);
            dfsss(i);
            dfsc(i,0);
            for(auto u:t){
                cost[u]=max(cost[u],dd[u]);
                // cout<<u<<' '<<cost[u]<<endl;
                if(cost[u]<mn){
                    mn=cost[u];
                    mni=u;
                }
            }
            rots.push_back({mn,mni});
        }
    }
    sort(rots.begin(),rots.end());
    reverse(rots.begin(),rots.end());
    for(int j=1;j<rots.size();j++){
        g[rots[j].second].push_back({rots[0].second,L});
        g[rots[0].second].push_back({rots[j].second,L});
    }
    dfss(0);
    dfss(mxi);
    return mxx;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfsss(int, int)':
dreaming.cpp:40:9: warning: unused variable 'mx' [-Wunused-variable]
   40 |     int mx=d;
      |         ^~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int j=1;j<rots.size();j++){
      |                 ~^~~~~~~~~~~~

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