제출 #550776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550776		CSQ31	Rail (IOI14_rail)	C++17	56 / 100	356 ms	98612 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int d[5001][5001];
void findLocation(int n, int f, int location[], int stype[])
{
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			d[i][j] = d[j][i] = getDistance(i,j);
		}
	}
	location[0] = f;
	stype[0] = 1;
	vector<int>mn(n,0);
	for(int i=0;i<n;i++){
		int c = 1e9;
		for(int j=0;j<n;j++){
			if(i==j)continue;
			if(c > d[i][j]){
				c = d[i][j];
				mn[i] = j;
			}
		}
	}
	int x = mn[0];
	stype[x] = 2;
	location[x] = f + d[x][0];
	vector<int>l,r;
	for(int i=0;i<n;i++){
		if(i==0 || i==x)continue;
		if(d[0][i] == d[0][x] + d[x][i])l.push_back(i);
		else r.push_back(i);
	}
	int c0 = 0,c1 = x;
	//for(int x:r)cout<<x<<'\n';
	while(!l.empty()){ //solbve for each block of (down,up)
		vector<int>tmp;
		for(int a:l){ //completing this block
			if(mn[a] == c0){
				stype[a] = 2;
				location[a] = location[c0] + d[c0][a];
			}else if(mn[a] == c1){
				stype[a] = 1;
				location[a] = location[c1] - d[c1][a];
			}else{
				tmp.push_back(a);
			}
		}
		if(!tmp.empty()){
			int c = 1e9;
			int can = 0;
			for(int a:tmp){
				if(c > d[a][c1]){
					c = d[a][c1];
					can = a;
				}
			}
			stype[can] = 1;
			location[can] = location[c1] - d[can][c1];
			c0 = can;
			c1 = mn[can];
			stype[c1] = 2;
			location[c1] = location[c0] + d[c0][c1];
			vector<int>tmp2;
			for(int a:tmp){
				if(a!=c0 && a!=c1)tmp2.push_back(a);
			}
			swap(tmp,tmp2);
		}
		swap(l,tmp);
	}
	c0 = 0;
	c1 = x;
	while(!r.empty()){
		vector<int>tmp;
		for(int a:r){ //completing this block
			if(mn[a] == c0){
				stype[a] = 2;
				location[a] = location[c0] + d[c0][a];
			}else if(mn[a] == c1){
				stype[a] = 1;
				location[a] = location[c1] - d[c1][a];
			}else{
				tmp.push_back(a);
			}
		}
		if(!tmp.empty()){
			int c = 1e9;
			int can = 0;
			for(int a:tmp){
				if(c > d[a][c0]){
					c = d[a][c0];
					can = a;
				}
			}
			stype[can] = 2;
			location[can] = location[c0] + d[can][c0];
			c0 = mn[can];
			c1 = can;
			stype[c0] = 1;
			location[c0] = location[c1] - d[c0][c1];
			vector<int>tmp2;
			for(int a:tmp){
				if(a!=c0 && a!=c1)tmp2.push_back(a);
			}
			swap(tmp,tmp2);
		}
		swap(r,tmp);
		
		
	}
	//for(int i=0;i<n;i++)cout<<stype[i]<<" "<<location[i]<<'\n';
}

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