Submission #50059

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
50059	2018-06-07T07:57:03 Z	dongwon0427	Race (IOI11_race)	C++11	Compilation error	0 ms	0 KB

race

/*
god taekyu
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n,m;
#define M 200005
vector<pii> graph[M];

int subsize[M];
int depth[M];
int del[M], par[M];
void init_subsize(int idx, int par_of_idx) {
    subsize[idx] = 1;
    par[idx] = par_of_idx;
    for(int i=0;i<graph[idx].size();i++) {
        int nxt = graph[idx][i].first;
        if(del[nxt] == 1) continue;
        if(nxt == par_of_idx) continue;
        init_subsize(nxt, idx);
        subsize[idx] += subsize[nxt];
    }
}
int find_centroid(int idx,int sz_tot) {
    for(int i=0;i<graph[idx].size();i++) {
        int nxt = graph[idx][i].first;
        if(del[nxt] == 1) continue;
        if(nxt == par[idx]) continue;

        if(subsize[nxt] * 2 > sz_tot) return find_centroid(nxt,sz_tot);
    }
    return idx;
}

pii que[M]; int quecnt;
int gaesu[M];
void init_depth(int idx,int par) {
    for(int i=0;i<graph[idx].size();i++) {
        int nxt = graph[idx][i].first;
        if(del[nxt] == 1) continue;
        if(nxt == par) continue;
        depth[nxt] = depth[idx] + graph[idx][i].second;
        gaesu[nxt] = gaesu[idx] + 1;
        que[quecnt++] = pii(depth[nxt] , gaesu[nxt]);
        init_depth(nxt,idx);
    }
}
int depth_checker[1000005];
int depth_checker_ans[1000005];
int depth_checker_cnt;
int ret = 2147483647;
void dfs(int idx) {
    init_subsize(idx, -1);
    int centroid = find_centroid(idx,subsize[idx]);

    depth[centroid] = 0;
    del[centroid] = 1;

    int mincnt = depth_checker_cnt;
    int ans = 2147483647;
    //cout<<"=============\n";
    for(int i=0;i<graph[centroid].size();i++) {
        int nxt = graph[centroid][i].first;
        if(del[nxt] == 1) continue;

        depth[nxt] = graph[centroid][i].second;
        gaesu[nxt] = 1;
        depth_checker_cnt++;

        quecnt = 0; que[quecnt++] = pii(depth[nxt] , gaesu[nxt]);
        init_depth(nxt,centroid);

        //cout<<depth_checker_cnt<<" : ";
        for(int i=0;i<quecnt;i++) {
            int val = que[i].first;
          //  cout<<val<<' ';
            if(m - val >=0 && depth_checker[m-val] > mincnt) {
                ans = min(ans , depth_checker_ans[m-val] + que[i].second);
            }
        }
        //cout<<'\n';
        for(int i=0;i<quecnt;i++) {
            int val = que[i].first;
            if(val > m) continue;
            if(depth_checker[val] <= mincnt
               ||
               depth_checker[val] > mincnt && depth_checker_ans[val] > que[i].second) {
                depth_checker_ans[val] = que[i].second;
                depth_checker[val] = depth_checker_cnt;
                //cout<<val<<" , "<<que[i].second<<"\n";
            }
        }
    }

    ret = min(ret, ans);
    //cout<<centroid<<' '<<ans<<'\n';
    //for(int i=0;i<n;i++) cout<<depth[i]<<' ';

    for(int i=0;i<graph[centroid].size();i++) {
        int nxt = graph[centroid][i].first;
        if(del[nxt] == 1) continue;

        dfs(nxt);
        //cout<<nxt;
    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n-1;i++) {
        int a,b,c;
        cin>>a>>b>>c;
        graph[a].push_back(pii(b,c));
        graph[b].push_back(pii(a,c));
    }

    dfs(0);
    if(ret == 2147483647) cout<<-1;
    else cout<<ret;
    return 0;
}

/*
god taekyu
*/

Compilation message

race.cpp: In function 'void init_subsize(int, int)':
race.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<graph[idx].size();i++) {
                 ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'int find_centroid(int, int)':
race.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<graph[idx].size();i++) {
                 ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'void init_depth(int, int)':
race.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<graph[idx].size();i++) {
                 ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int)':
race.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<graph[centroid].size();i++) {
                 ~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp:91:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                depth_checker[val] > mincnt && depth_checker_ans[val] > que[i].second) {
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<graph[centroid].size();i++) {
                 ~^~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccF6sNJX.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccC2JA0b.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccC2JA0b.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status