oj.uz

답안 #902113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902113 2024-01-10T06:06:49 Z UmairAhmadMirza 철로 (IOI14_rail) C++14
30 / 100
 114 ms 1164 KB 
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int const N=5005;
int dist1[N];
int dist2[N];
bool done[N];
int getDistance(int i, int j);
void findLocation(int n, int firloc, int location[], int stype[]){
	int fir=0;
	location[0]=firloc;
	stype[0]=1;
	done[fir]=1;
	if(n==1)
		return;
	set<pair<int,int>> dd;
	for (int i = 1; i < n; ++i){
		dist1[i]=getDistance(0,i);
		dd.insert({dist1[i],i});
	}
	// cout<<endl;
	auto p=*(dd.begin());
	int sec=p.second;
	for (int i = 1; i < n; ++i)
	{
		if(i==sec)
			continue;
		dist2[i]=getDistance(sec,i);
		if(dist2[i]<dist1[i] && dist2[i]>dist1[sec])
			dd.erase({dist1[i],i});
	}
	while(dd.size()){
		auto p=*(dd.begin());
		dd.erase(p);
		int seco=p.second;
		location[seco]=p.first+location[0];
		stype[seco]=2;
		done[seco]=1;
		// cout<<"mini"<<endl;
		// cout<<location[0]<<endl;
		// cout<<seco<<' '<<p.first<<endl;
		for (int i = 1; i < n; ++i)
		{
			if(done[i])
				continue;
			if(dist2[i]<dist1[i] && dist2[i]-dist1[seco]>0)
				continue;
			int dis=getDistance(seco,i);
			if(dist1[i]-dist1[seco]==dis){
				done[i]=1;
				location[i]=location[seco]-dis;
				stype[i]=1;
				dd.erase({dist1[i],i});
			}
		}
	}
	for (int i = 1; i < n; ++i)
		if(done[i]==0)
			dd.insert({dist2[i],i});
	while(dd.size()){
		auto p=*(dd.begin());
		dd.erase(p);
		int firo=p.second;
		location[firo]=location[sec]-p.first;
		stype[firo]=1;
		done[firo]=1;
		for (int i = 1; i < n; ++i)
		{
			if(done[i])
				continue;
			int dis=getDistance(firo,i);
			if(dist2[i]-dist2[firo]==dis){
				done[i]=1;
				location[i]=location[firo]+dis;
				stype[i]=2;
				dd.erase({dist2[i],i});
			}
		}
	}
	// for (int i = 0; i < n; ++i)
	// 	cout<<location[i]<<' '<<stype[i]<<endl;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 912 KB Output is correct
2 Correct 95 ms 856 KB Output is correct
3 Correct 102 ms 852 KB Output is correct
4 Correct 102 ms 848 KB Output is correct
5 Correct 114 ms 1104 KB Output is correct
6 Incorrect 101 ms 912 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 908 KB Output is correct
2 Correct 95 ms 904 KB Output is correct
3 Correct 106 ms 1164 KB Output is correct
4 Correct 102 ms 852 KB Output is correct
5 Correct 111 ms 912 KB Output is correct
6 Incorrect 98 ms 916 KB Output isn't correct
7 Halted 0 ms 0 KB -