답안 #100402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100402	2019-03-10T22:50:33 Z	SuperJumbo	경주 (Race) (IOI11_race)	C++14	컴파일 오류	0 ms	0 KB

race

#include <bits/stdc++.h>
#define NMAX 1000001
#define inf (INT_MAX>>2)
#define ll long long
#define add push_back
#define mp make_pair
#include "race.h"
using namespace std;
#define min(a,b) (a > b ? b : a) 
vector<pair<int,int>> g[NMAX];
int tot, k, ans; 
int sz[NMAX], cen[NMAX];
int all[NMAX];
void dfs(int node,int par){
    sz[node] = 1;
    for(auto e:g[node]){
    	int x = e.first;
        if(x == par || cen[x] )continue;
        dfs(x,node);
        sz[node] += sz[x];
    }
    tot = max(tot,sz[node]);
}
int centroid(int node,int par){
    for(auto e:g[node]){
    	int x = e.first;
        if(x!=par && sz[x]> tot/2 && !cen[x]){
            return centroid(x,node);
        }
    }
    cen[node] = 1;
    return node;
}
void dfs2(int node, int par, int cc, int len, unordered_map<int,int> & sub){
	if(len == k) ans = min(ans, cc);
	if(len >= k) return;
	if(all[k-len]) ans = min(ans,all[k-len]+cc);
	if(!sub[len])  sub[len] = cc;
	sub[len] = min(sub[len],cc);
	for(auto e:g[node]){
		int x = e.first;
		if(!cen[x] && x != par)
			dfs2(x,node,cc+1,len + e.second);
	}
 
 
}
void dcmp(int node,int par){
    tot = 0;
    dfs(node,par);
    int c = centroid(node,par);
    memset(all,0,sizeof(all));
    for(auto e :g[c]){
    	int x  = e.first;
    	if(cen[x])continue;
    	unordered_map<int,int> sub;
    	dfs2(x,c,1,e.second, sub);
    	for(auto u:sub) 
    		all[u.first] = all[u.first] == 0 ? u.second : min(all[u.first],u.second);
    }
    for(auto e:g[c]){
    	int x = e.first;
    	if(!cen[x]) dcmp(x,c);
    }
}
int best_path(int n,int K,int h[][2] ,int L[]) {
	k  = K;
    g.resize(n);
    for(int i = 0 ;i<n-1;i++){
    	int u = h[i][0], v = h[i][1];
        g[u].add(mp(v,L[i]));g[v].add(mp(u,L[i]));
    }
    memset(cen,0,sizeof(cen));
    ans = inf;
    dcmp(0,-1);
  	ans = ans == inf ? -1: ans;
    return ans;
}

Compilation message

race.cpp: In function 'void dfs2(int, int, int, int, std::unordered_map<int, int>&)':
race.cpp:43:35: error: too few arguments to function 'void dfs2(int, int, int, int, std::unordered_map<int, int>&)'
    dfs2(x,node,cc+1,len + e.second);
                                   ^
race.cpp:34:6: note: declared here
 void dfs2(int node, int par, int cc, int len, unordered_map<int,int> & sub){
      ^~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:68:7: error: request for member 'resize' in 'g', which is of non-class type 'std::vector<std::pair<int, int> > [1000001]'
     g.resize(n);
       ^~~~~~