oj.uz

Submission #12911

# Submission time Handle Problem Language Result Execution time Memory
12911 2015-01-20T05:31:30 Z gs14004 Race (IOI11_race) C++
0 / 100
 17 ms 6816 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
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 = 0;
    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;
}

vector<int> solve(int p){
    int mid = get_mid(p);
    kill[mid] = 1;
    vector<int> v(k+1,1e9);
    v[0] = 0;
    for (int i=0; i<graph[mid].size(); i++) {
        if(kill[graph[mid][i].second]) continue;
        vector<int> u = solve(graph[mid][i].second);
        int l = graph[mid][i].first;
        for (int j=0; j<=k - l; j++) {
            ret = min(ret,v[k-j-l] + u[j] + 1);
        }
        for (int j=0; j<=k - l; j++) {
            v[j+l] = min(v[j+l],u[j] + 1);
        }
    }
    return v;
}

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

Compilation message

race.cpp: In function 'int dfs(int, int)':
race.cpp:23: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:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<new_vis.size(); i++) {
                   ~^~~~~~~~~~~~~~~
race.cpp: In function 'std::vector<int> solve(int)':
race.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[mid].size(); i++) {
                   ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6612 KB Output is correct
2 Correct 15 ms 6632 KB Output is correct
3 Incorrect 17 ms 6816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6612 KB Output is correct
2 Correct 15 ms 6632 KB Output is correct
3 Incorrect 17 ms 6816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6612 KB Output is correct
2 Correct 15 ms 6632 KB Output is correct
3 Incorrect 17 ms 6816 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6612 KB Output is correct
2 Correct 15 ms 6632 KB Output is correct
3 Incorrect 17 ms 6816 KB Output isn't correct
4 Halted 0 ms 0 KB -