Submission #16516

#	Time	Username	Problem	Language	Result	Execution time	Memory
16516		khsoo01	Race (IOI11_race)	C++98	100 / 100	1247 ms	48368 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define INF 987654321
using namespace std;
vector<int>cg[200005],cv[200005];
stack<int>used;
int ch[200005],p[1000005],n,cn,k,ans=INF;
bool col[200005];

void count_num(int idx,int prev) {
    int i; cn++;
    for(i=0;i<cg[idx].size();i++) {
        if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
            count_num(cg[idx][i],idx);
        }
    }
}

pair<int,int> find_cen(int idx,int prev) {
    pair<int,int> ret(INF,-1),tmp;
    int i,cc=1,mc=0;
    for(i=0;i<cg[idx].size();i++) {
        if(col[cg[idx][i]] || cg[idx][i]==prev) continue;
        tmp=find_cen(cg[idx][i],idx);
        if(tmp.first<ret.first) ret=tmp;
        mc=max(mc,ch[cg[idx][i]]);
        cc+=ch[cg[idx][i]];
    }
    mc=max(mc,cn-cc);
    if(mc<ret.first) ret={mc,idx};
    ch[idx]=cc;
    return ret;
}

void match(int idx,int prev,int cnt,int len) {
    if(len>k) return;
    int i; ans=min(ans,p[k-len]+cnt);
    for(i=0;i<cg[idx].size();i++) {
        if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
            match(cg[idx][i],idx,cnt+1,len+cv[idx][i]);
        }
    }
}

void apply(int idx,int prev,int cnt,int len) {
    if(len>k) return;
    int i; p[len]=min(p[len],cnt); used.push(len);
    for(i=0;i<cg[idx].size();i++) {
        if(!col[cg[idx][i]] && cg[idx][i]!=prev) {
            apply(cg[idx][i],idx,cnt+1,len+cv[idx][i]);
        }
    }
}

void dnc(int idx) {
    while(!used.empty()) {p[used.top()]=INF; used.pop();}
    p[0]=0;
    cn=0; count_num(idx,-1);
    int i,cen=find_cen(idx,-1).second;
    for(i=0;i<cg[cen].size();i++) {
        if(col[cg[cen][i]])continue;
        match(cg[cen][i],cen,1,cv[cen][i]);
        apply(cg[cen][i],cen,1,cv[cen][i]);
    }
    col[cen]=1;
    for(i=0;i<cg[cen].size();i++) {
        if(!col[cg[cen][i]]) {
            dnc(cg[cen][i]);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    int i; n=N; k=K;
    for(i=0;i<n-1;i++) {
        cg[H[i][0]].push_back(H[i][1]);
        cv[H[i][0]].push_back(L[i]);
        cg[H[i][1]].push_back(H[i][0]);
        cv[H[i][1]].push_back(L[i]);
    }
    for(i=1;i<=k;i++)p[i]=INF;
    dnc(0);
    return (ans==INF?-1:ans);
}

Compilation message (stderr)

race.cpp: In function 'void count_num(int, int)':
race.cpp:12:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'std::pair<int, int> find_cen(int, int)':
race.cpp:22:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'void match(int, int, int, int)':
race.cpp:38:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'void apply(int, int, int, int)':
race.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[idx].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp: In function 'void dnc(int)':
race.cpp:60:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[cen].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp:66:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[cen].size();i++) {
             ~^~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57