제출 #706931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706931		Nhoksocqt1	Race (IOI11_race)	C++17	컴파일 에러	0 ms	0 KiB

race

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;

set<ii> G[MAXN];
int sz[MAXN], dp[5 * MAXN], numNode, pathLen;

int dfsSize(int u, int p) {
    sz[u] = 1;
    for (auto it : G[u]) {
        int v(it.fi);
        if(v != p)
            sz[u] += dfsSize(v, u);
    }

    return sz[u];
}

int centroid(int u, int p, int nSize) {
    for (auto it : G[u]) {
        int v(it.fi);
        if(v != p && sz[v] > nSize / 2)
            return centroid(v, u, nSize);
    }

    return u;
}

int dfs(int u, int p, int len, int cntNode, vector<ii> &dis) {
    if(len > pathLen)
        return 1e9+7;

    dis.push_back({len, cntNode + 1});
    int res = min(int(1e9)+7, cntNode + dp[pathLen - len]);
    for (auto it : G[u]) {
        int v(it.fi), w(it.se);
        if(v != p)
            res = min(res, dfs(v, u, len + w, cntNode + 1, dis));
    }

    return res;
}

int build(int u, int p) {
    int nSize = dfsSize(u, p);
    int c = centroid(u, p, nSize);

    dp[0] = 1;
    int res(1e9+7);
    vector<int> tmp;
    for (auto it : G[c]) {
        vector<ii> tmpn;
        int v(it.fi), w(it.se);
        res = min(res, dfs(v, c, w, 1, tmpn));
        while(tmpn.size()) {
            tmp.push_back(tmpn.back().fi);
            minimize(dp[tmp.back()], tmpn.back().se);
            tmpn.pop_back();
        }
    }

    for (int it = 0; it < int(tmp.size()); ++it) {
        int x(tmp[it]);
        dp[x] = 1e9+7;
    }

    vector<ii> tmpg(G[c].begin(), G[c].end());
    for (int it = 0; it < int(tmpg.size()); ++it) {
        int v(tmpg[it].fi), w(tmpg[it].se);
        G[c].erase({v, w});
        G[v].erase({c, w});
        res = min(res, build(v, c));
    }

    return res;
}

void process() {
    cin >> numNode >> pathLen;
    for (int i = 1; i < numNode; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].insert({v, w});
        G[v].insert({u, w});
    }

    for (int i = 0; i <= pathLen; ++i)
        dp[i] = 1e9+7;

    int res = build(0, -1);
    cout << (res >= 1e9 ? -1 : res - 1) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("RACE.inp", "r", stdin);
//    freopen("RACE.out", "w", stdout);

    process();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
race.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
/usr/bin/ld: /tmp/ccG8DElE.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccvtK3cE.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccvtK3cE.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