Submission #344128

#	Time	Username	Problem	Language	Result	Execution time	Memory
344128		katearima	Dreaming (IOI13_dreaming)	C++14	100 / 100	138 ms	17556 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int R=1e5+5;
vector<pair<int,int>> adj[R];
int dpD1[R], dpD2[R], dpU[R], mn,mx;
vector<bool> visited(R);
vector<int> ans;
void dfsDown(int k){
    visited[k]=true;
    for(auto u:adj[k]){
        int dist=u.ss; int ch=u.ff;
        if(visited[ch]) continue;
        dfsDown(ch);
        if(dpD1[ch]+dist > dpD1[k]){
            dpD2[k]=dpD1[k];
            dpD1[k]=dpD1[ch]+dist;
        }
        else if(dpD1[ch]+dist > dpD2[k]){
            dpD2[k]=dpD1[ch]+dist;
        }
    }

}
void dfsUp(int k, int par){
    for(auto u:adj[k]){
        int dist=u.ss; int ch=u.ff;
        if(ch==par) continue;
        dpU[ch]=dpU[k]+dist;
        if(dpD1[k]==dpD1[ch]+dist) dpU[ch]=max(dpU[ch], dpD2[k]+dist);
        else dpU[ch]=max(dpU[ch], dpD1[k]+dist);
        //cout<<"child: " << ch << "parent: "<< k<<  "UP" << dpU[ch]<<endl;
        dfsUp(ch, k);
    }
    mn=min(mn, max(dpD1[k], dpU[k]));
    mx=max(mx, dpD1[k]+dpU[k]);
}
int travelTime(int n, int m, int l, int a[], int b[], int time[]) {
    for(int i=0; i<m; i++){
        adj[a[i]].push_back(make_pair(b[i], time[i]));
        adj[b[i]].push_back(make_pair(a[i], time[i]));
    }
    for(int i=0; i<n; i++){
        if(visited[i]) continue;
        mn=INT_MAX;
        dfsDown(i);
        dfsUp(i, -1);
        //cout<<mn<<endl;
        ans.push_back(mn);

    }

    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());
    if(ans.size()>2) mx=max(mx, ans[1]+ans[2]+2*l);
    if(ans.size()>1) mx=max(mx,  ans[0]+ans[1]+l);
    return mx;
    return 42;
}

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