oj.uz

답안 #1005390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005390 2024-06-22T11:53:45 Z nikd 경주 (Race) (IOI11_race) C++17
0 / 100
 1 ms 2396 KB 
// https://oj.uz/problem/view/IOI11_race
#include <bits/stdc++.h>
#define ll long long
using namespace std;



vector<vector<pair<int, int>>> adj;
int n, k;
vector<bool> is_rem;
vector<int> sz;
vector<ll> distL; //ll
vector<int> dist;
vector<array<int, 4>> k_dist;
vector<int> to_rem;
int sol;
int cont = 0;



void get_sz(int v, int e){
    sz[v]=1;
    for(auto edge: adj[v]){
        int u = edge.first;
        if(u==e||is_rem[u]) continue;
        get_sz(u, v); sz[v] += sz[u];
    }
    return;
}

void get_dist(int v, int e, int sb){
    if(distL[v]<=k){
        if(dist[v]<k_dist[distL[v]][0]){
            if(k_dist[distL[v]][1]!=sb){
                k_dist[distL[v]][3] = k_dist[distL[v]][1];
                k_dist[distL[v]][2] = k_dist[distL[v]][0];
            }
            k_dist[distL[v]][0] = dist[v];
            k_dist[distL[v]][1] = sb;
            
        }
        else if(k_dist[distL[v]][1]!=sb && dist[v]<k_dist[distL[v]][2]){
            k_dist[distL[v]][2] = dist[v];
            k_dist[distL[v]][3] = sb;

        }

        if(k_dist[k-distL[v]][1]!=sb && k_dist[k-distL[v]][0] != INT_MAX){
            sol = min(sol, k_dist[k-distL[v]][0] + dist[v]);
        }
        else if(k_dist[k-distL[v]][2] != INT_MAX ){
            sol = min(sol, k_dist[k-distL[v]][3] + dist[v]);
        }

        
    }
    to_rem[cont++]=v;
    for(auto edge: adj[v]){
        int u = edge.first;
        if(u==e||is_rem[u]) continue;
        dist[u]=dist[v]+1;
        distL[u]=distL[v]+edge.second;
        if(v==e) sb = u;
        get_dist(u, v, sb);
    }
    return;
}


int find_centr(int v, int e, int siz){
    for(auto edge: adj[v]){
        int u = edge.first;
        if(u==e||is_rem[u]) continue;
        if(sz[u] > siz/2) return find_centr(u, v, siz);
    }
    return v;
}

void decompose(int v, int siz){
    get_sz(v, v);
    int c = find_centr(v, v, siz);
    dist[c]=0; distL[c]=0;
    cont = 0;
    get_dist(c, c, -1);
    for(int i = 0; i<siz; i++){
        if(distL[to_rem[i]]<=k){
            k_dist[distL[to_rem[i]]]={INT_MAX, INT_MAX, INT_MAX, INT_MAX};
        }
    }
    get_sz(c, c);


    is_rem[c]=1;
    for(auto edge: adj[c]){
        int u = edge.first;
        if(is_rem[u]) continue;
        decompose(u, sz[u]);
    }
}


int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K;
    adj.resize(N);
    sz.resize(n);
    is_rem.resize(n, 0);
    distL.resize(n);
    dist.resize(n);
    
    k_dist.resize(k+1, {INT_MAX, INT_MAX, INT_MAX, INT_MAX});
    to_rem.resize(n);
    sol = INT_MAX;
    for(int i = 0; i<n-1; i++){
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    decompose(0, n);

    return (sol==INT_MAX ? -1 : sol);

}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Incorrect 1 ms 2392 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Incorrect 1 ms 2392 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Incorrect 1 ms 2392 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Incorrect 1 ms 2392 KB Output isn't correct
15 Halted 0 ms 0 KB -