제출 #782805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782805		berr	경주 (Race) (IOI11_race)	C++17	100 / 100	288 ms	36236 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 2e5+37;
int mi = 1e7, n, k, p;
vector<array<int, 2>> adj[N];
vector<int> s(N), vis2(N);
vector<int> best((int)1e6+37, 1e7); 
vector<array<int, 2>> mp;
vector<int> pff;

void dfs(int v, int p){
    int pf=0;
    s[v] = 1;

    for(auto i: adj[v]){
        if(vis2[i[0]]||i[0]==p) continue;
        pf++;
        dfs(i[0], v); s[v]+=s[i[0]];
    }

}
int dfs2(int v, int p, int gh){

    for(auto i: adj[v]){
        if(vis2[i[0]]||i[0]==p) continue;
        if(s[i[0]]>=gh/2) return dfs2(i[0], v, gh);
    }
    return v;
}

void dfs3(int v,  int dist, int z, int p){
   // cout<<v<<" "<<dist<<" "<<z<<"\n";
    if(dist<=k){
	    mp.push_back({dist, z});
	    
	    for(auto i: adj[v]){

	        if(vis2[i[0]]||i[0]==p) continue;

	        dfs3(i[0], dist+i[1], z+1, v);
	    }
	}
}

void dfs4(int v){

    for(auto pf: adj[v]){
        if(vis2[pf[0]]) continue;   
        mp.clear();

        dfs3(pf[0], pf[1], 1, v);
       

        for(auto i: mp){
	        if(i[0]>k) continue;
	        if(best[k-i[0]]!=1e7){
	       		mi=min(mi, i[1]+best[k-i[0]]);
	        }
        }
        for(auto i: mp){
        	if(i[0]<=k){
	        	best[i[0]]=min(i[1], best[i[0]]);
	        	pff.push_back(i[0]);
        	}
        }
    }
}


void gh(int v){

    dfs(v, v); 

    int x = dfs2(v, v, s[v]);
    dfs4(x);

    for(auto i:pff) if(i<=k)best[i]=1e7;
    pff.clear();
	
	vis2[x]=1; best[0]=0;
	for(auto i: adj[x]){
		if(!vis2[i[0]]) gh(i[0]);
	}
}

int best_path(int N, int K, int a[][2], int l[])
{	
	best[0]=0;
    n = N, k = K;

    for(int i= 0; i < n-1; i++){
        int x=a[i][0], y=a[i][1], z=l[i];
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }

    p=1;
    gh(0);

    if(mi==1e7) return -1;
    return mi;
}

void f(){
	#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
}
/*
signed main()
{
    f();
    int n, k; cin >> n >> k;
    int a[n-1][2], l[n-1];
    for(int i=0; i<n-1; i++){
        cin>>a[i][0]>>a[i][1] >> l[i];
    }

   cout<< best_path(n, k, a, l);

   cerr<<(float)clock()/CLOCKS_PER_SEC;
}

    */

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

race.cpp: In function 'void f()':
race.cpp:107:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp:108:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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