제출 #1236054

#제출 시각아이디문제언어결과실행 시간메모리
1236054allin27xRace (IOI11_race)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
const int mod = 1e9+7;
#define forn(i,n) for(int i=0; i<n; i++)
#define readv(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
#define readvv(a,n,m) vector<vector<int>> a(n,vector<int>(m));forn(i,n)forn(j,m)cin>>a[i][j];
#define all(a) a.begin(), a.end()
#define _max(x,y) x = max(x,y)
#define _min(x,y) x = min(x,y)
// #define f first
// #define s second

const int MAXN = 2e5+5;
const int MAXM = 1e6+5;
vector<pair<int,int>> adj[MAXN];
int sbt[MAXN];
vector<int> ch[MAXN];
vector<pair<int,int>> inf[MAXN];
int pn[MAXM];
int rem[MAXN];
int mk[MAXN];
int par[MAXN];
void dfs(int i, int p) {
	sbt[i] = 1;
	for (auto [c, w]: adj[i]) {
		if (c==p || rem[c]) continue;
		dfs(c, i);
		sbt[i] += sbt[c];
	}
}

int ctd(int i, int p, int sz) {
	for (auto [c,w] : adj[i]) {
		if (c==p || rem[c]) continue;
		if (2*sbt[c] > sz) return ctd(c, i, sz);
	}
	return i;
}


void calc(int i, int p, int dsw, int dse, int tp) {
	if (dsw >= MAXM) dsw = MAXM;
	if (i!=p) inf[tp]. push_back({dsw, dse});
	for (auto [c,w]: adj[i]) {
		if (c==p || rem[c]) continue;
		calc(c, i, dsw+w, dse+1, tp);
	}
}

int build(int i) {
	dfs(i, 0);
	int x = ctd(i, i, sbt[i]);
	rem[x] = 1;
	for (auto [c,w] : adj[x]) {
		if (rem[c]) continue;
		ch[x].push_back(build(c));
		par[ch[x].back()] = x;
	}
	return x;
}

int k;
int ans = MAXM;
void solve(int i) {
	rem[i] = 1;
	for (auto [c,w]:adj[i]) {
		if (rem[c]) continue;
		int tp = c;
		while (par[tp] != i) tp = par[tp];
		calc(c, i, w, 1, tp);
	}
	for (int c: ch[i]) {
		for (auto [dsw, dse]: inf[c]) {
			if (dsw >= MAXM) continue;
			pn[dsw] = MAXM;
			if (dsw <= k) pn[k-dsw] = MAXM;
		}
	}
	pn[0] = 0;
	for (int c: ch[i]) {
		for (auto [dsw, dse]: inf[c]) {
			if (dsw > k) continue;
			ans = min(ans, pn[k-dsw] + dse);
		}
		for (auto[dsw, dse]: inf[c]) {
			if (dsw > k) continue;
			pn[dsw] = min(pn[dsw], dse);
		}
	}
	for (int c: ch[i]) solve(c);
}

int best_path(int N, int K, int H[][2], int L[])
{
	k = K;
	for (int i=0; i<N-1; i++) {
		H[i][0] ++; H[i][1] ++;
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	int centr = build(1);
	for (int i=0; i<N+3; i++) rem[i] = 0;
	solve(centr);
	if (ans < MAXM)return ans;
	return -1;
}

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 500000

static int N, K;
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,&K));
	for(i=0; i<N-1; i++)
		my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
	my_assert(1==scanf("%d",&solution));
}

int main()
{
	int ans;
	read_input();
	ans = best_path(N,K,H,L);
	if(ans==solution)
		printf("Correct.\n");
	else
		printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

	return 0;
}

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

/usr/bin/ld: /tmp/ccp4rTvi.o: in function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'; /tmp/ccOyGjod.o:race.cpp:(.text+0x210): first defined here
/usr/bin/ld: /tmp/ccp4rTvi.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccOyGjod.o:race.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status