Submission #645846

#	Time	Username	Problem	Language	Result	Execution time	Memory
645846		Vectorized	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

//#define ll long long
#define maxN 2000005
using namespace std;
#include <iostream>
#include <iostream>
#include<vector>
#include <climits>
#include<set>
#include<map>
int n, k;
//first = node, second = weight
vector<pair<int ,int>> adj[maxN];
map<int, int> sets[maxN];
vector<int> ord;
int p[maxN], lzW[maxN], lzN[maxN];

void dfs(int node, int parent){
    p[node] = parent;
    for(pair<int, int> j: adj[node]){
        if(j.first != parent){
            dfs(j.first, node);
            ord.push_back(j.first);
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back(make_pair(b, w));
        adj[b].push_back(make_pair(a, w));
    }
    dfs(0, -1);
    p[0] = -1;
    ord.push_back(0);
    int ans = INT_MAX;
    for (int i = 0; i < n; ++i) {
        int node = ord[i];
        if(adj[node].size() == 1 && node != 0){
            lzW[node] = 0;
            lzN[node] = 0;
            continue;
        }
        int bn = -1, bz = -1, bw = 0;
        for(pair<int, int> j : adj[node]){
            if(j.first == p[node]) continue;
            if((int)sets[j.first].size() > bz){
                bz = (int)sets[j.first].size();
                bn = j.first;
                bw = j.second;
            }
        }
        swap(sets[bn], sets[node]);
        lzW[node] = lzW[bn] + bw;
        lzN[node] = lzN[bn] + 1;
        sets[node][bw - lzW[node]] = 1 - lzN[node];
        for(pair<int, int> j: adj[node]){
            if(j.first == p[node] || j.first == bn) continue;
            for (auto const& a : sets[j.first]){
                int f = k - (a.first + lzW[j.first] + j.second) - lzW[node];
                if(sets[node].find(f) != sets[node].end()){
                    ans = min(ans, a.second + lzN[j.first] + 1 + sets[node][f] + lzN[node]);
                }
            }
            for (auto const& a : sets[j.first]){
                int f = (a.first + lzW[j.first] + j.second) - lzW[node];
                if(sets[node].find(f) != sets[node].end()){
                    sets[node][f] = min(sets[node][f], a.second + lzN[j.first] + 1 - lzN[node]);
                }else{
                    sets[node][f] = a.second + lzN[j.first] + 1 - lzN[node];
                }
            }
            int f = k - j.second;
            if(sets[node].find(f) != sets[node].end()){
                ans = min(ans, sets[node][f] + lzN[node] + 1);
            }
            sets[node][j.second - lzW[node]] = 1 - lzN[node];
        }
        if(sets[node].find(k - lzW[node]) != sets[node].end()){
            ans = min(ans, sets[node][k - lzW[node]] + lzN[node]);
        }
    }
    cout << ans << "\n";
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cctmO6EI.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLeOdyK.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccLeOdyK.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status