Submission #97566

#	Time	Username	Problem	Language	Result	Execution time	Memory
97566		georgerapeanu	Dreaming (IOI13_dreaming)	C++11	24 / 100	90 ms	15224 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

const int NMAX = 1e5;

pair<int,int> link[NMAX + 5];

vector< pair<int,int> > graph[NMAX + 5];

bool viz[NMAX + 5];

struct data_t{
    int best_dist;
    int node;
};


data_t dfs(int nod,int tata){
    viz[nod] = true;
    data_t ans;
    ans.node = nod;
    ans.best_dist = 0;

    link[nod] = {-1,-1};

    for(auto it:graph[nod]){
        if(it.first == tata){
            continue;
        }
        data_t tmp = dfs(it.first,nod);
        if(ans.best_dist <= tmp.best_dist + it.second){
            ans.best_dist = tmp.best_dist + it.second;
            ans.node = tmp.node;
            link[nod] = it;
        }
    }

    return ans;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int ans = 0;

    for(int i = 0;i < M;i++){
        graph[A[i]].push_back({B[i],T[i]});
        graph[B[i]].push_back({A[i],T[i]});
    }

    vector<int> d;

    for(int i = 0;i < N;i++){
        if(viz[i]){
            continue;
        }

        data_t tmp = dfs(i,0);
        data_t aux = dfs(tmp.node,0);

        vector<int> diam;
        int len = 0;
        diam.push_back(0);
        for(int node = tmp.node;link[node].first != -1;node = link[node].first){
            diam.push_back(link[node].second);
            len += diam.back();
        }

        ans = max(ans,len);

        int best = 1 << 30;
        int pref = 0;

        for(int i = 0;i < (int)diam.size();i++){
            pref += diam[i];
            best = min(best,max(pref,len - pref));
        }
        
        d.push_back(best);
    }

    priority_queue<int,vector<int>,greater<int> > h;

    for(auto it:d){
        h.push(it);
    } 

    while((int)h.size() > 1){
        int a = h.top();h.pop();
        int b = h.top();h.pop();

        ans = max(ans,a + b + L);

        b = max(b,a + L);

        h.push(b);
    }

    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:63:16: warning: variable 'aux' set but not used [-Wunused-but-set-variable]
         data_t aux = dfs(tmp.node,0);
                ^~~

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