Submission #43665

#	Time	Username	Problem	Language	Result	Execution time	Memory
43665		smu201111192	Race (IOI11_race)	C++14	100 / 100	2546 ms	58372 KiB

race

#include "race.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 300001;
vector<pair<int,ll> > tree[MAXN];
int sz[MAXN],kill[MAXN];
void addEdge(int u,int v,ll w){
    tree[u].push_back(make_pair(v,w));
    tree[v].push_back(make_pair(u,w));
}
void dfs(int here,int dad){
    sz[here] = 1;
    for(int i=0;i<tree[here].size();i++){
        int there = tree[here][i].first;
        if(there == dad || kill[there]) continue;
        dfs(there,here);
        sz[here] += sz[there];
    }
}
int getCenter(int here,int dad,int cap){
    for(int i=0;i<tree[here].size();i++){
        int there = tree[here][i].first;
        if(there == dad || kill[there]) continue;
        if(sz[there] > cap) return getCenter(there,here,cap);
    }
    return here;
}
void dfs2(int here,int dad,ll dep,map<ll,ll> &tcnt,int d){
    if(tcnt.find(dep) == tcnt.end()) tcnt[dep] = d;
    else{ tcnt[dep] = min(tcnt[dep],1LL * d); }
    for(int i=0;i<tree[here].size();i++){
        int there = tree[here][i].first;
        ll w = tree[here][i].second;
        if(there == dad || kill[there]) continue;
        dfs2(there,here,dep+w,tcnt,d+1);
    }
}
long long ans;
void decompose(int root,ll K){
    dfs(root,-1);
    int center = getCenter(root,-1,sz[root]/2);
    map<ll,ll> cnt;
    cnt[0] = 0;
    for(int i=0;i<tree[center].size();i++){
        int there = tree[center][i].first;
        ll w = tree[center][i].second;
        if(kill[there]) continue;
        map<ll,ll> tcnt;
        dfs2(there,center,w,tcnt,1);
        for(auto it = tcnt.begin(); it!= tcnt.end(); it++){
            ll need = K - it->first;
            if(cnt.find(need) != cnt.end()) ans = min(ans,it->second + cnt[need]);
        }
        for(auto it = tcnt.begin(); it!= tcnt.end(); it++){
            if(cnt.find(it->first) == cnt.end()) cnt[it->first] = it->second;
            else{ cnt[it->first] = min(cnt[it->first],it->second); }
        }
    }
    kill[center] = 1;
    for(int i=0;i<tree[center].size();i++){
        int there = tree[center][i].first;
        if(kill[there]) continue;
        decompose(there,K);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    ans = 4e18;
    for(int i=0;i<N-1;i++){
        addEdge(H[i][0],H[i][1],L[i]);
    }
    decompose(0,K);
    if(ans == 4e18) ans = -1;
    return (int)ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[here].size();i++){
                 ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'int getCenter(int, int, int)':
race.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[here].size();i++){
                 ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int, long long int, std::map<long long int, long long int>&, int)':
race.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[here].size();i++){
                 ~^~~~~~~~~~~~~~~~~~
race.cpp: In function 'void decompose(int, long long int)':
race.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[center].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~~
race.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tree[center].size();i++){
                 ~^~~~~~~~~~~~~~~~~~~~

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