Submission #12915

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
12915	2015-01-20T08:39:44 Z	gs14004	Race (IOI11_race)	C++	Compilation error	0 ms	0 KB

race

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
typedef pair<int,int> pi;

vector<pi> graph[200005];

int ret = 1e9;
int size[200005], maxtree[200005];
int kill[200005];
int k;

vector<int> new_vis;

int dfs(int p, int pa){
    if(kill[p]) return 0;
    new_vis.push_back(p);
    int cs = 1;
    int maxv = 0;
    for (int i=0; i<graph[p].size(); i++) {
        if(graph[p][i].second == pa) continue;
        int t = dfs(graph[p][i].second,p);
        maxv = max(t,maxv);
        cs += t;
    }
    maxtree[p] = maxv;
    return size[p] = cs;
}

int get_mid(int p){
    new_vis.clear();
    memset(size,0,sizeof(size));
    memset(maxtree,0,sizeof(maxtree));
    int full = dfs(p,-1);
    int mid_pos = 0, mid_res =1e9;
    for (int i=0; i<new_vis.size(); i++) {
        maxtree[new_vis[i]] = max(maxtree[new_vis[i]],full - size[new_vis[i]]);
        if(mid_res > maxtree[new_vis[i]]){
            mid_pos = new_vis[i];
            mid_res = maxtree[mid_pos];
        }
    }
    return mid_pos;
}
int v[1000005];

void solve(int p){
    int mid = get_mid(p);
    kill[mid] = 1;
    memset(v,63,sizeof(v));
    v[0] = 0;
    for (int i=0; i<graph[mid].size(); i++) {
        if(kill[graph[mid][i].second]) continue;
        queue<int> q,d,p,l;
        vector<int> cd1, cd2;
        if(graph[mid][i].first > k) continue;
        q.push(graph[mid][i].second);
        d.push(graph[mid][i].first);
        l.push(1);
        p.push(mid);
        while (!q.empty()) {
            int qf = q.front();
            int df = d.front();
            int pf = p.front();
            int lf = l.front();
            cd1.push_back(df);
            cd2.push_back(lf);
            ret = min(v[k-df] + lf,ret);
            q.pop();
            d.pop();
            p.pop();
            l.pop();
            for (int i=0; i<graph[qf].size(); i++) {
                int pos = graph[qf][i].second;
                if(kill[pos] || pos == pf) continue;
                if(df + graph[qf][i].first > k) continue;
                q.push(pos);
                d.push(df + graph[qf][i].first);
                p.push(qf);
                l.push(lf + 1);
            }
        }
        for (int i=0; i<cd1.size(); i++) {
            v[cd1[i]] = min(v[cd1[i]],cd2[i]);
        }
    }
    for (int i=0; i<graph[mid].size(); i++) {
        if(kill[graph[mid][i].second]) continue;
        solve(graph[mid][i].second);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    for (int i=0; i<N-1; i++) {
        graph[H[i][0]].push_back(pi(L[i],H[i][1]));
        graph[H[i][1]].push_back(pi(L[i],H[i][0]));
    }
    k = K;
    solve(0);
    if(ret > 1e8) return -1;
    return ret;
}

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    int h[200005][2], l[200005];
    for (int i=0; i<n-1; i++) {
        scanf("%d %d %d",&h[i][0],&h[i][1],&l[i]);
    }
    printf("%d",best_path(n,k,h,l));
}

Compilation message

race.cpp: In function 'int dfs(int, int)':
race.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[p].size(); i++) {
                   ~^~~~~~~~~~~~~~~~
race.cpp: In function 'int get_mid(int)':
race.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<new_vis.size(); i++) {
                   ~^~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[mid].size(); i++) {
                   ~^~~~~~~~~~~~~~~~~~
race.cpp:77:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i=0; i<graph[qf].size(); i++) {
                           ~^~~~~~~~~~~~~~~~~
race.cpp:87:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<cd1.size(); i++) {
                       ~^~~~~~~~~~~
race.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[mid].size(); i++) {
                   ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'int main()':
race.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
race.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&h[i][0],&h[i][1],&l[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccAvBpkJ.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccv4Nb8c.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status