제출 #1369460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369460		c12	경주 (Race) (IOI11_race)	C++20	43 / 100	3093 ms	32480 KiB

race

#pragma GCC optimize("O3","unrolled-loop")
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;
const int MAXK = 1e6+5;

// OVERALL
int K;
int mn = INT_MAX;

// GRAPH
vector<pair<int,int>> adj[MAXN];

// CENTROID
vector<int> child_centroid[MAXN];
int sz[MAXN];
int vis[MAXN];

// CAL DIST
int dist[MAXK];
pair<int,int> rollback_list[MAXN];
int rollback_ptr = 0;
int rolldist[MAXN];
int rolldist_ptr = 0;

void init(){
    fill(adj,adj+MAXN,vector<pair<int,int>>());
    
    fill(child_centroid,child_centroid+MAXN,vector<int>());
    memset(sz,0,sizeof(sz));
    memset(vis,0,sizeof(vis));

    fill(dist,dist+MAXK,INT_MAX/3);
    memset(rollback_list,0,sizeof(rollback_list));
    rollback_ptr = 0;
    memset(rolldist,0,sizeof(rolldist));
    rolldist_ptr = 0;
}

// CENTROID
int get_centriod(int u,int p,int n){
    for(auto x : adj[u]){
        int v = x.first;
        if(v == p || vis[v]) continue;
        if(sz[v] > n/2){
            return get_centriod(v,u,n);
        }
    }
    return u;
}

void get_size(int u,int p){
    sz[u] = 1;
    for(auto x : adj[u]){
        int v = x.first;
        if(v == p || vis[v]) continue;
        get_size(v,u);
        sz[u] += sz[v];
    }
}

void dfs(int u,int p,int cnt,int cost){
    if(cost > K) return;

    if(dist[K-cost] != INT_MAX/3) mn = min(mn,dist[K-cost] + cnt);
    
    rollback_list[rollback_ptr++] = {cnt,cost};
    rolldist[rolldist_ptr++] = cost;

    for(auto x : adj[u]){
        if(x.first == p || vis[x.first]) continue;
        dfs(x.first,u,cnt+1,cost+x.second);
    }
}

void cal_centroid(int u){
    get_size(u,-1);
    int n = sz[u];
    u = get_centriod(u,-1,n);
    
    vis[u] = 1;

    dist[0] = 0;
    for(auto x : adj[u]){
        dfs(x.first,u,1,x.second);
        while(rollback_ptr > 0){
            rollback_ptr--;
            dist[rollback_list[rollback_ptr].second] = min(dist[rollback_list[rollback_ptr].second],rollback_list[rollback_ptr].first);
        }
    }
    dist[0] = INT_MAX/3;

    while(rolldist_ptr > 0){
        rolldist_ptr--;
        dist[rolldist[rolldist_ptr]] = INT_MAX/3;
    }

    for(auto x : adj[u]){
        if(vis[x.first]) continue;

        cal_centroid(x.first);
    }
}    

int best_path(int N, int _K, int H[][2], int L[])
{
    init();
    
    K = _K;

    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]});
    }

    cal_centroid(0);

    if(mn == INT_MAX) return -1;
    return mn;
}

// #define MAX_N 500000

// static int N, P;
// static int H[MAX_N][2];
// static int L[MAX_N];
// static int solution;

// inline 
// void my_assert(int e) {if (!e) abort();}

// void read_input()
// {
//   int i;
//   my_assert(2==scanf("%d %d",&N,&P));
//   for(i=0; i<N-1; i++)
//     my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// }

// int main()
// {
//   int ans;
//   read_input();
//   ans = best_path(N,P,H,L);

//   cout << ans << '\n';
  
//   return 0;
// }
// /*
// 11 12
// 0 1 3
// 0 2 4
// 2 3 5
// 3 4 4
// 4 5 6
// 0 6 3
// 6 7 2
// 6 8 5
// 8 9 6
// 8 10 7
// */

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

race.cpp:1:42: warning: bad option '-funrolled-loop' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3","unrolled-loop")
      |                                          ^
race.cpp:28:11: warning: bad option '-funrolled-loop' to attribute 'optimize' [-Wattributes]
   28 | void init(){
      |           ^
race.cpp:43:35: warning: bad option '-funrolled-loop' to attribute 'optimize' [-Wattributes]
   43 | int get_centriod(int u,int p,int n){
      |                                   ^
race.cpp:54:26: warning: bad option '-funrolled-loop' to attribute 'optimize' [-Wattributes]
   54 | void get_size(int u,int p){
      |                          ^
race.cpp:64:38: warning: bad option '-funrolled-loop' to attribute 'optimize' [-Wattributes]
   64 | void dfs(int u,int p,int cnt,int cost){
      |                                      ^
race.cpp:78:24: warning: bad option '-funrolled-loop' to attribute 'optimize' [-Wattributes]
   78 | void cal_centroid(int u){
      |                        ^
race.cpp:107:49: warning: bad option '-funrolled-loop' to attribute 'optimize' [-Wattributes]
  107 | int best_path(int N, int _K, int H[][2], int L[])
      |                                                 ^

• 서브태스크 1: 9 / 9
• 서브태스크 2: 12 / 12
• 서브태스크 3: 22 / 22
• 서브태스크 4: 0 / 57