Submission #1111177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111177		FubuGold	Race (IOI11_race)	C++14	0 / 100	5 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) continue;
            int tmp = get_len(k - x);
            if (tmp != INF) ans = min(ans,tmp + 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;
        }
    }
    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));
    nd[u].mp[0] = 0;
}

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));
   }
   cal_sz(1,-1);
   dfs(1,-1);
   if (ans == INF) return -1;
   return ans;
}

// int main() {
//     cin.tie(0) -> sync_with_stdio(0);
//     cin >> n >> k;
//     for (int i=1;i<n;i++) {
//         int x,y,w; cin >> x >> y >> w;
//         x++,y++;
//         adj[x].push_back(make_pair(y,w));
//         adj[y].push_back(make_pair(x,w));
//     }
// //    if (k == 0) {
// //        cout << 0;
// //    }
//     cal_sz(1,-1);
//     dfs(1,-1);
//     if (ans == INF) ans = -1;
//     cout << ans;
//     return 0;
// }

Compilation message (stderr)

race.cpp: In function 'int cal_sz(int, int)':
race.cpp:47: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]
   47 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int)':
race.cpp:58: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]
   58 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
race.cpp:71: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]
   71 |         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