oj.uz

Submission #16515

# Submission time Handle Problem Language Result Execution time Memory
16515 2015-08-27T01:04:36 Z khsoo01 Race (IOI11_race) C++
0 / 100
 10 ms 9980 KB 
#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();}
    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

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:59:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[cen].size();i++) {
             ~^~~~~~~~~~~~~~~
race.cpp:65:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<cg[cen].size();i++) {
             ~^~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9884 KB Output is correct
4 Correct 9 ms 9960 KB Output is correct
5 Correct 9 ms 9960 KB Output is correct
6 Correct 10 ms 9960 KB Output is correct
7 Correct 10 ms 9960 KB Output is correct
8 Correct 10 ms 9960 KB Output is correct
9 Correct 9 ms 9964 KB Output is correct
10 Correct 9 ms 9980 KB Output is correct
11 Incorrect 9 ms 9980 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9884 KB Output is correct
4 Correct 9 ms 9960 KB Output is correct
5 Correct 9 ms 9960 KB Output is correct
6 Correct 10 ms 9960 KB Output is correct
7 Correct 10 ms 9960 KB Output is correct
8 Correct 10 ms 9960 KB Output is correct
9 Correct 9 ms 9964 KB Output is correct
10 Correct 9 ms 9980 KB Output is correct
11 Incorrect 9 ms 9980 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9884 KB Output is correct
4 Correct 9 ms 9960 KB Output is correct
5 Correct 9 ms 9960 KB Output is correct
6 Correct 10 ms 9960 KB Output is correct
7 Correct 10 ms 9960 KB Output is correct
8 Correct 10 ms 9960 KB Output is correct
9 Correct 9 ms 9964 KB Output is correct
10 Correct 9 ms 9980 KB Output is correct
11 Incorrect 9 ms 9980 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9884 KB Output is correct
4 Correct 9 ms 9960 KB Output is correct
5 Correct 9 ms 9960 KB Output is correct
6 Correct 10 ms 9960 KB Output is correct
7 Correct 10 ms 9960 KB Output is correct
8 Correct 10 ms 9960 KB Output is correct
9 Correct 9 ms 9964 KB Output is correct
10 Correct 9 ms 9980 KB Output is correct
11 Incorrect 9 ms 9980 KB Output isn't correct
12 Halted 0 ms 0 KB -