Submission #282608

#	Time	Username	Problem	Language	Result	Execution time	Memory
282608		shayan_p	Rail (IOI14_rail)	C++14	100 / 100	117 ms	2460 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[]){
    fill(stype, stype + n, -1);
    
    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;
    }
    stype[mnid] = 2;
    location[mnid] = location[0] + A[mnid];

    int Lid = 0, Rid = mnid, Mid = Lid;
    for(int i = 0; i < n; i++){
	if(i != Lid && i != Rid){
	    B[i] = ask(Rid, i);
	    if(abs(A[i] - B[i]) == location[Rid] - location[Lid] && B[i] < A[i] && B[i] < location[Rid] - location[Lid]){
		stype[i] = 1;
		location[i] = location[Rid] - B[i];
		if(Mid == Lid || B[Mid] > B[i])
		    Mid = i;
	    }		
	}
    }
    vector<pii> L, R;
    for(int i = 0; i < n; i++){
	if(stype[i] == -1){
	    if(abs(A[i] - B[i]) != location[Rid] - location[Lid] || A[i] < B[i])
		R.PB({A[i] - (location[Rid] - location[Lid]), i});
	    else
		L.PB({B[i] - (location[Rid] - location[Lid]), 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: 26 / 26
• Subtask 4: 44 / 44