제출 #387413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387413		alishahali1382	도시들 (IOI15_towns)	C++14	25 / 100	30 ms	620 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto abcd_:abcd) cerr<<abcd_<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const int N=120;

int n, m, k, ans;
int D[N][N], pref[N], suff[N];
vector<int> path, vec[N], candid;

int ask(int i, int j){
	if (i==j) return 0;
	if (i>j) swap(i, j);
	if (D[i][j]==-1) D[i][j]=getDistance(i, j);
	return D[i][j];
}

int hubDistance(int n, int sub){
	memset(D, -1, sizeof(D));
	for (int i=0; i<n; i++) vec[i].clear();
	path.clear();
	candid.clear();

	int X=0, Y=0;
	for (int i=1; i<n; i++) if (ask(0, i)>ask(0, X)) X=i;
	for (int i=1; i<n; i++) if (ask(X, i)>ask(X, Y)) Y=i;
	ans=inf;
	for (int i=0; i<n; i++){
		int a=(ask(X, i)+ask(X, Y)-ask(Y, i))/2;
		int b=ask(X, Y)-a, c=ask(X, i)-a;
		ans=min(ans, max(a, b));
		path.pb(a);
	}
	if (sub<=2) return ans;
	sort(all(path));
	path.resize(unique(all(path))-path.begin());
	for (int i=0; i<n; i++){
		int a=(ask(X, i)+ask(X, Y)-ask(Y, i))/2;
		int b=ask(X, Y)-a, c=ask(X, i)-a;
		vec[lower_bound(all(path), a)-path.begin()].pb(i);
	}
	// 2n-3 so far
	debugv(path)
	int len=path.size()-1;
	pref[0]=suff[len]=1;
	for (int i=1; i<=len; i++) pref[i]=pref[i-1]+SZ(vec[i]);
	for (int i=len; ~i; i--) suff[i]=suff[i+1]+SZ(vec[i]);
	for (int i=1; i<len; i++) if (max(path[i], ask(X, Y)-path[i])==ans){
		// center at distance vec[i]
		// check for centroid
		if (pref[i-1]>n/2 || suff[i+1]>n/2) continue ;
		if (sub==4){
			// faghat ye branch
			if (SZ(vec[i])>n/2) continue ;
			return -ans;
		}
		cout<<1/0;
	}


	
	return ans;
}

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:29:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   29 | int hubDistance(int n, int sub){
      |                               ^
towns.cpp:18:5: note: shadowed declaration is here
   18 | int n, m, k, ans;
      |     ^
towns.cpp:41:22: warning: unused variable 'c' [-Wunused-variable]
   41 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |                      ^
towns.cpp:50:7: warning: unused variable 'b' [-Wunused-variable]
   50 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |       ^
towns.cpp:50:22: warning: unused variable 'c' [-Wunused-variable]
   50 |   int b=ask(X, Y)-a, c=ask(X, i)-a;
      |                      ^
towns.cpp:55:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   55 |  int len=path.size()-1;
      |          ~~~~~~~~~~~^~
towns.cpp:68:10: warning: division by zero [-Wdiv-by-zero]
   68 |   cout<<1/0;
      |         ~^~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39