Submission #29433

#	Time	Username	Problem	Language	Result	Execution time	Memory
29433		Nikefor	Race (IOI11_race)	C++98	21 / 100	3030 ms	13176 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define inf 1<<22
using namespace std;
int globalMin = inf;
int target;
int W[1000001];
set<int> used;
vector< pair<int,int> > adj[200001];
void centroid(int n);
int sizer(int n, int road) {
    int sum = 0;
    for(int i=0; i<adj[n].size(); i++) {
        if(used.find(adj[n][i].first)==used.end() and (adj[n][i].second!=road)) sum+=sizer(adj[n][i].first, adj[n][i].second);
    }
    return sum+1;

}
int best_path(int N, int K, int H[][2], int L[])
{
    target = K;
    for(int i=0; i<N-1; i++) {
        int v1 = H[i][0], v2 = H[i][1];
        adj[v1].push_back(make_pair(v2, i));
        adj[v2].push_back(make_pair(v1, i));
    }
    for(int i=0; i<N-1; i++) W[i] = L[i];
    centroid(0);
    return globalMin<inf?globalMin:-1;
}
int A[1000002];
int tmp[1000002];
void DFS(int c, int road, int cost, int edge) {
    if(tmp[cost]>edge) tmp[cost] = edge;
    if(tmp[cost]+A[target-cost]<globalMin) globalMin = tmp[cost]+A[target-cost];
    for(int i =0; i< adj[c].size(); i++) {
        if(used.find(adj[c][i].first)!=used.end()) continue;
        if(adj[c][i].second!=road and ((cost+W[adj[c][i].second])<=target) ) DFS(adj[c][i].first, adj[c][i].second, cost+W[adj[c][i].second], edge+1);
    }

}
int centroidfinder(int n) {
    int siz = sizer(n,-1);
    for(int i=0; i<adj[n].size(); i++) {
        if(used.find(adj[n][i].first)!=used.end()) continue;
        if(sizer(adj[n][i].first, adj[n][i].second) > siz/2) return centroidfinder(adj[n][i].first);
    }
    return n;
}
void centroid(int n) {
    if( sizer(n, -1)<2 ) return;
   // int siz = sizer(n,-1);
    int c = centroidfinder(n);
    int kol = adj[c].size();
    for(int i=1; i<target+1; i++) A[i] = tmp[i] = inf;
    A[0] = tmp[0]=0;
    for(int i= 0; i<kol; i++) {
        if(used.find(adj[c][i].first)!=used.end() ) continue;
        for(int j=1; j<=target; j++) tmp[j] = inf;
        if(W[adj[c][i].second] <= target )DFS(adj[c][i].first, adj[c][i].second, W[adj[c][i].second], 1);
      //  for(int j=1; j<target; j++) if((tmp[j]+A[target-j])<globalMin) globalMin = tmp[j]+A[target-j];
        for(int j=1; j<target; j++) if(tmp[j]<A[j]) A[j] = tmp[j];

    }
    used.insert(c);
    for(int i=0; i<kol; i++) if(used.find(adj[c][i].first)==used.end() ) centroid(adj[c][i].first);

}

Compilation message (stderr)

race.cpp: In function 'int sizer(int, int)':
race.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj[n].size(); i++) {
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'void DFS(int, int, int, int)':
race.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i =0; i< adj[c].size(); i++) {
                   ~^~~~~~~~~~~~~~~
race.cpp: In function 'int centroidfinder(int)':
race.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj[n].size(); i++) {
                  ~^~~~~~~~~~~~~~

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