제출 #282574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282574		shayan_p	철로 (IOI14_rail)	C++14	30 / 100	108 ms	4600 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"

#define F first
#define S second
#define sz(s) (int(s.size()))
#define PB push_back
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int A[maxn], B[maxn];

map<pii, int> mp;
int ask(int a, int b){
    if(a == b)
	return 0;
    if(mp.count({a, b}))
	return mp[{a, b}];
    return mp[{a, b}] = mp[{b, a}] = getDistance(a, b);
}

void findLocation(int n, int p, int location[], int stype[]){
    stype[0] = 1;
    location[0] = p;
    if(n == 1)
	return;
    int mnid = 1;
    for(int i = 1; i < n; i++){
	A[i] = ask(0, i);
	if(A[mnid] > A[i])
	    mnid = i;
    }
    int p2 = p + A[mnid];
    stype[mnid] = 2;
    location[mnid] = p2;

    int Lid = -1, Rid = mnid;
    for(int i = 0; i < n; i++){
	if(i != mnid){
	    B[i] = ask(mnid, i);
	    if(Lid == -1 || B[i] < B[Lid])
		Lid = i;
	}
    }
    stype[Lid] = 1;
    location[Lid] = p2 - B[Lid];
    for(int i = 0; i < n; i++){
	if(i != Lid)
	    A[i] = ask(Lid, i);
    }
	
    vector<pii> L, R;
    for(int i = 0; i < n; i++){
	if(i != Lid && i != Rid){
	    if(A[i] < B[i]){
		assert(B[i] == A[i] + p2 -p);
		R.PB({A[i] - (p2 - p), i});
	    }
	    else{
		assert(A[i] == B[i] + p2 -p);
		L.PB({B[i] - (p2 - p), i});
	    }		
	}
    }

    {
	vector<pii> dis;
	sort(L.begin(), L.end());
	for(pii p : L){
	    vector<int> candid;
	    for(int i = 0; i < sz(dis); i++){
		if(dis[i].F >= p.F)
		    continue;
		int bk = dis[i].F - (p.F - dis[i].F);
		if(i == 0 && bk <= 0)
		    continue;
		if(i != 0 && dis[i-1].F >= bk)
		    continue;
		candid.PB(bk);
	    }
	    if(sz(candid)){
		int num = ask(dis.back().S, p.S);
		int bk = dis.back().F - num;
		bool any = 0;
		for(int x : candid)
		    any|= bk == x;
		candid.clear();
		if(any)
		    candid.PB(bk);
	    }
	    if(sz(candid)){
		int bk = candid.back();
		location[p.S] = location[Lid] - bk;
		stype[p.S] = 2;
	    }
	    else{
		dis.PB(p);
		location[p.S] = location[Lid] - p.F;
		stype[p.S] = 1;
	    }
	}
    }

    {
	vector<pii> dis;
	sort(R.begin(), R.end());
	for(pii p : R){
	    vector<int> candid;
	    for(int i = 0; i < sz(dis); i++){
		if(dis[i].F >= p.F)
		    continue;
		int bk = dis[i].F - (p.F - dis[i].F);
		if(i == 0 && bk <= 0)
		    continue;
		if(i != 0 && dis[i-1].F >= bk)
		    continue;
		candid.PB(bk);
	    }
	    if(sz(candid)){
		int num = ask(dis.back().S, p.S);
		int bk = dis.back().F - num;
		bool any = 0;
		for(int x : candid)
		    any|= bk == x;
		candid.clear();
		if(any)
		    candid.PB(bk);
	    }
	    if(sz(candid)){
		int bk = candid.back();
		location[p.S] = location[Rid] + bk;
		stype[p.S] = 1;
	    }
	    else{
		dis.PB(p);
		location[p.S] = location[Rid] + p.F;
		stype[p.S] = 2;
	    }
	}
    }
}

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