제출 #97571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97571		georgerapeanu	꿈 (IOI13_dreaming)	C++11	54 / 100	85 ms	15224 KiB

dreaming

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

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);
    }

    sort(d.begin(),d.end());

    int st = 0,dr = (int)d.size() - 1;

    while(st < dr){
        if(d[dr] >= d[st] + L){
            ans = max(ans,d[dr] + d[st] + L);
            st++;
        }
        else{
            ans = max(ans,d[dr] + d[dr - 1] + L);
            d[dr - 1] = max(d[dr],d[dr - 1] + L);
            dr--;
        }
    }

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62: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: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 0 / 23