Submission #498251

#	Time	Username	Problem	Language	Result	Execution time	Memory
498251		XII	Race (IOI11_race)	C++17	100 / 100	451 ms	33024 KiB

race

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

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

//#define IOS cin.tie(0)->sync_with_stdio(false);
//#define PROB "IOI11_race"
//void Fi(){
//    if(fopen(PROB".inp", "r")){
//        freopen(PROB".inp", "r", stdin);
//        freopen(PROB".out", "w", stdout);
//    }
//}

const int INF = 1e9;
const int N = 2e5 + 1;
const int K = 1e6 + 1;

vector<int> adj[N], wei[N];

int ans, RLen;

bool chking[N];
int Q[N];
int par[N], len[N], dep[N], sz[N];

int bfs(int s){
    int cur, top = 0;
    Q[++top] = s;
    par[top] = 0;
    len[top] = dep[top] = 0;
    sz[top] = 1;

    while(cur < top){
        int u = Q[++cur];
        FOR(i, 0, adj[u].size()){
            if(!chking[adj[u][i]] && Q[par[cur]] != adj[u][i]){
                Q[++top] = adj[u][i];
                par[top] = cur;
                len[top] = len[cur] + wei[u][i];
                dep[top] = dep[cur] + 1;
                sz[top] = 1;
            }
        }
    }
    FORD(i, top, 2) sz[par[i]] += sz[i];
    return top;
}

int properCentroid(int n){
    int m = n + 1, c;
    FORU(i, 1, n){
        if(m > sz[i] && sz[i] > n / 2){
            m = sz[i];
            c = Q[i];
        }
    }
    return c;
}

int mnE[K], upd[N];

void dfs(int s){
    int n = bfs(s);
    if(n == 1) return;
    int c = properCentroid(n), cnt = 0;
    chking[c] = true;

    FOR(i, 0, adj[c].size()){
        if(!chking[adj[c][i]]) dfs(adj[c][i]);
    }

    FOR(i, 0, adj[c].size()){
        if(chking[adj[c][i]]) continue;
        n = bfs(adj[c][i]);
        FORU(j, 1, n){
            len[j] += wei[c][i], dep[j] += 1;
            if(len[j] > RLen) continue;
            if(len[j] == RLen) ans = min(ans, dep[j]);
            else if(mnE[RLen - len[j]]){
                ans = min(ans, dep[j] + mnE[RLen - len[j]]);
            }
        }
        FORU(j, 1, n){
            if(len[j] <= RLen && (mnE[len[j]] == 0 || mnE[len[j]] > dep[j])){
                mnE[len[j]] = dep[j];
                upd[++cnt] = len[j];
            }
        }
    }

    chking[c] = false;
    FORU(i, 1, cnt) mnE[upd[i]] = 0;
}

int best_path(int N, int K, int H[][2], int L[]){
    RLen = K;
    FOR(i, 0, N - 1){
        adj[H[i][0]].eb(H[i][1]);
        adj[H[i][1]].eb(H[i][0]);
        wei[H[i][0]].eb(L[i]);
        wei[H[i][1]].eb(L[i]);
    }
    ans = INF;
    dfs(0);
    return (ans != INF) ? ans : -1;
}

//int n, k, H[N][2], L[N];
//
//int main(){
//    IOS;
//    Fi();
//    cin >> n >> k;
//    FOR(i, 0, n - 1){
//        cin >> H[i][0] >> H[i][1];
//    }
//    FOR(i, 0, n - 1) cin >> L[i];
//    cout << best_path(n, k, H, L);
//    return 0;
//}

Compilation message (stderr)

race.cpp: In function 'int bfs(int)':
race.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
race.cpp:47:9: note: in expansion of macro 'FOR'
   47 |         FOR(i, 0, adj[u].size()){
      |         ^~~
race.cpp: In function 'void dfs(int)':
race.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
race.cpp:80:5: note: in expansion of macro 'FOR'
   80 |     FOR(i, 0, adj[c].size()){
      |     ^~~
race.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
race.cpp:84:5: note: in expansion of macro 'FOR'
   84 |     FOR(i, 0, adj[c].size()){
      |     ^~~
race.cpp: In function 'int bfs(int)':
race.cpp:39:9: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     int cur, top = 0;
      |         ^~~
race.cpp: In function 'int properCentroid(int)':
race.cpp:69:12: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     return c;
      |            ^

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