Submission #1269343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269343		pedro	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define ii pair<int, int>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define INF 99999999999999
#define length second

ll n, k, bestSol = INF;
vector<vector<pair<int, ll>>> adj; // node -> {node, length}
vector<pair<int, ll>> smallest; // [lenght] -> {flag, edgeCount}
vector<ii> nodeInfo; // node -> {edgeCount, length}
vi sizes;
vector<bool> wasRoot;
int centroid;

int flag = 0;

void dfs1(int node, int parent, int edgeCount, int lenSum) {
    nodeInfo[node] = {edgeCount, lenSum};
    //printf("   dfs1 n=%d, EC=%d, LS=%d\n", node, edgeCount, lenSum);

    if (lenSum > k) return; // questionável

    //cout << "   smallest = ";
    // for (int i=0; i<10; i++) {
    //     cout << smallest[i].second << " ";
    // }
    // cout << endl;

    ll s = smallest[k-lenSum].first == flag ? smallest[k-lenSum].second : INF;

    if (k - lenSum >= 0 && s + edgeCount < bestSol) {
        bestSol = smallest[k-lenSum].second + edgeCount;
        //cout << "   bestSol atualizada = " << bestSol << endl;
    }

    for (auto child : adj[node]) if (child.first != parent)
        dfs1(child.first, node, edgeCount + 1, lenSum + child.second);
}

void dfs2(int node, int parent) {
    ii info = nodeInfo[node];

    if (info.length > k) return;

    if (smallest[info.length].first != flag || smallest[info.length].second > info.first) { // atualizar a flag
        smallest[info.length].first = flag;
        smallest[info.length].second = info.first;
    }

    for (auto child : adj[node]) if (child.first != parent)
        dfs2(child.first, node);
}

void subtreeSize(int node, int parent) {
    int s = 1;
    for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != parent && !wasRoot[adj[node][i].first]) {
        subtreeSize(adj[node][i].first, node);
        s += sizes[adj[node][i].first];
    }
    sizes[node] = s;
}

void findCentroid(int node, int parent, int numVert) {
    centroid = node;

    ii max = { -1, -1 }; // val, node;
    bool isCentroid = true;
    for (int i=0; i<adj[node].size(); i++) if (adj[node][i].first != node && !wasRoot[adj[node][i].first]) {
        if (sizes[adj[node][i].first] > max.first) max = { sizes[adj[node][i].first], adj[node][i].first };
        if (sizes[adj[node][i].first] > numVert / 2) isCentroid = false;
    }
    
    if (!isCentroid) {
        sizes[node] = numVert - sizes[node] + 1;
        findCentroid(max.second, node, numVert);
    }
}

int main() {    

    scanf("%lld %lld", &n, &k);
    printf("%lld %lld\n", n, k);
    adj = vector<vector<pair<int, ll>>>(n);
    smallest = vector<pair<int, ll>>(1000001, {0, INF});
    for (int i=0; i<n-1; i++) {
        int a, b, l;
        scanf("%d %d %d", &a, &b, &l);
        printf("%d %d %d\n", a, b, l);
        adj[a].push_back({b, l});
        adj[b].push_back({a, l});
    }

    nodeInfo = vector<ii>(n, {-1, -1});

    queue<int> queue;
    wasRoot = vector<bool>(n, false);

    queue.push(0);
    while (!queue.empty()) {
        int currRoot = queue.front();

        sizes = vi(n, 0);
        subtreeSize(currRoot, -1);
        // for (int i=0; i<n; i++) cout << sizes[i] << " ";
        // cout << endl;
        int numVertSubTree = sizes[currRoot];
        findCentroid(currRoot, -1, numVertSubTree);
        // cout << "centroid = " << centroid << endl;

        currRoot = centroid;
        wasRoot[currRoot] = true;
        // cout << "currRoot = " << currRoot << endl;
        smallest[0] = {flag, 0};
        queue.pop();
        for (auto child : adj[currRoot]) if (!wasRoot[child.first]) {
            queue.push(child.first);
            dfs1(child.first, currRoot, 1, child.second);
            dfs2(child.first, currRoot);
            //cout << "smallest dfs2 = ";
            // for (int i=0; i<10; i++) {
            //     cout << smallest[i].second << " ";
            // }
            // cout << endl;
            //printf("Melhor solucao apos dfs2(%d) = %lld\n", child.first, bestSol);
        }

        flag++;
    }

    if (bestSol == INF) printf("-1\n");
    else printf("%lld\n", bestSol);

    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
race.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%d %d %d", &a, &b, &l);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccYupiJA.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccPFcNQu.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccYupiJA.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