Submission #1111136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111136		FubuGold	Race (IOI11_race)	C++14	0 / 100	4 ms	22096 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200000;
const int INF = 1e9 + 5;

vector<pair<int,int>> adj[MAXN+1];
int n;
long long k;
int ans = INF;

struct Node {
    int offset_len = 0;
    long long offset_weight = 0;
    map<long long,int> mp;

    int get_len(long long x) {
        x -= offset_weight;
        auto it = mp.find(x);
        if (it == mp.end()) return INF;
        return it->second + offset_len;
    }

    void merge_node(Node &nd) {
        for (auto it = nd.mp.begin(); it != nd.mp.end(); it++) {
            long long x = it->first + nd.offset_weight;
            int l = it->second + nd.offset_len;
            if (x <= k) {
                int tmp = get_len(k - x);
                if (tmp != INF) ans = min(ans,tmp + offset_len + l);
            }
            x -= offset_weight;
            l -= offset_len;
            auto tmp_it = mp.find(x);
            if (tmp_it == mp.end()) mp[x] = l;
            else tmp_it->second = min(tmp_it->second,l);
        }
    }
};

Node nd[MAXN+1];
int sz[MAXN+1];

int cal_sz(int u,int p) {
    sz[u] = 1;
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i].first;
        if (v == p) continue;
        sz[u] += cal_sz(v,u);
    }
    return sz[u];
}

void dfs(int u,int p) {
    int mx_v = -1;
    int mx_v_w = 0;
    for (int i=0;i<adj[u].size();i++) {
        int v = adj[u][i].first;
        if (v == p) continue;
        dfs(v,u);
        if (mx_v == -1 || sz[mx_v] < v) {
            mx_v = v;
            mx_v_w = adj[u][i].second;
        }
    }
    nd[u].mp[0] = 0;
    if (mx_v != -1) {
        swap(nd[mx_v],nd[u]);
        nd[u].offset_len++;
        nd[u].offset_weight += mx_v_w;
        for (int i=0;i<adj[u].size();i++) {
            int v = adj[u][i].first;
            if (v == p || v == mx_v) continue;
            nd[v].offset_len++;
            nd[v].offset_weight += adj[u][i].second;
            nd[u].merge_node(nd[v]);
        }
    }
    ans = min(ans,nd[u].get_len(k));
//    cout << '\n';
//    cout << u << ' ' << mx_v << ' ' << nd[u].offset_len << ' ' << nd[u].offset_weight << '\n';
//    for (auto debug_x : nd[u].mp) {
//        cout << debug_x.first << ' ' << debug_x.second << '\n';
//    }
}

int best_path(int _n,int _k,int h[][2],int l[]) {
    n = _n;
    k = _k;
    for (int i=0;i<n-1;i++) {
        int x = h[i][0], y = h[i][1];
        int w = l[i];
        x++,y++;
        adj[x].push_back(make_pair(y,w));
        adj[y].push_back(make_pair(x,w));
    }
    if (k == 0) return 0;
    cal_sz(1,-1);
    dfs(1,-1);
    if (ans == INF) return -1;
    return ans;
}

//int _h[MAXN+1][2],_l[MAXN+1];

//int main() {
//    cin.tie(0) -> sync_with_stdio(0);
//    int t,c; cin >> t >> c;
//    for (int i=0;i<t-1;i++) {
//        cin >> _h[i][0] >> _h[i][1];
//    }
//    for (int i=0;i<t-1;i++) cin >> _l[i];
//    cout << best_path(t,c,_h,_l);
//    return 0;
//}

Compilation message (stderr)

race.cpp: In function 'int cal_sz(int, int)':
race.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int)':
race.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
race.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i=0;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~

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