제출 #1013419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013419		pcc	철로 (IOI14_rail)	C++17	8 / 100	117 ms	203092 KiB

rail

#include "rail.h"

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 5050;
int dp[mxn][mxn];
pii ans[mxn];

int Ask(int a,int b){
	return dp[a][b] == -1?dp[a][b] = dp[b][a] = getDistance(a,b):dp[a][b];
}

void Answer(int id,int pos,int tp){
	cerr<<"ANS: "<<id<<','<<pos<<','<<tp<<endl;
	if(ans[id].fs != -1)cerr<<"REPEATED ANSWER: "<<id<<endl;
	assert(ans[id].fs == -1);
	ans[id] = pii(pos,tp);
}

int d1[mxn],d2[mxn];

void findLocation(int N, int ori, int location[], int stype[]){
	memset(dp,-1,sizeof(dp));
	for(auto &i:ans)i = pii(-1,-1);
	vector<pii> da;
	for(int i = 1;i<N;i++){
		da.push_back(pii(Ask(0,i),i));
		d1[i] = Ask(0,i);
	}
	sort(da.begin(),da.end());
	int a = 0,b = da[0].sc;
	cerr<<"[a,b]: "<<a<<','<<b<<endl;
	Answer(a,ori,1);
	Answer(b,ori+da[0].fs,2);
	cerr<<"INIT DONE!"<<endl;
	vector<int> vl,vr;
	for(int i = 0;i<N;i++){
		if(i == b||i == a)continue;
		d2[i] = Ask(b,i);
		if(d1[i]>d2[i])vl.push_back(i);
		else vr.push_back(i);
		if(d1[i]>d2[i])cerr<<"VL add: "<<i<<endl;
		else cerr<<"VR add: "<<i<<endl;
	}
	sort(vl.begin(),vl.end(),[](int a,int b){return d2[a]<d2[b];});
	sort(vr.begin(),vr.end(),[](int a,int b){return d1[a]<d2[b];});
	int lp = a;
	for(auto &now:vl){
		if(Ask(lp,b)+Ask(lp,now) != Ask(b,now)){
			Answer(now,ans[b].fs-Ask(b,now),1);
			lp = now;
		}
		else{
			Answer(now,ans[lp].fs+Ask(lp,now),2);
		}
	}
	int rp = b;
	for(auto &now:vr){
		if(Ask(a,rp)+Ask(rp,now) != Ask(a,now)){
			Answer(now,ans[a].fs+Ask(a,now),2);
			rp = now;
		}
		else{
			Answer(now,ans[rp].fs-Ask(rp,now),1);
		}
	}
	for(int i = 0;i<N;i++){
		assert(ans[i].fs != -1);
		location[i] = ans[i].fs;
		stype[i] = ans[i].sc;
	}
	return;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44