Submission #745652

#	Time	Username	Problem	Language	Result	Execution time	Memory
745652		Username4132	Rail (IOI14_rail)	C++14	30 / 100	331 ms	98816 KiB

rail

#include "rail.h"
#include<iostream>
#include<vector>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN=5010, INF=1000000010;
int *rel, *res, count, le[2], ri[2];
int n, dis[MAXN][MAXN];
bool vis[MAXN];
vector<pii> g[MAXN];

void dfs(int v){
    vis[v]=true, ++count;
    for(pii to:g[v]) if(!vis[to.F]){
        if(res[v]==1) rel[to.F]=rel[v]+to.S;
        else rel[to.F]=rel[v]-to.S;
        int tp=(res[v]==1);
        if(rel[le[tp]]>rel[to.F]) le[tp]=to.F;
        if(rel[ri[tp]]<rel[to.F]) ri[tp]=to.F;
        res[to.F]=tp+1;
        dfs(to.F);
    }
}

void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    forn(i, n) forsn(j, i, n) dis[i][j]=dis[j][i]=getDistance(i, j);
    forn(i, n){
        int mn=INF, ind=-1;
        forn(j, n) if(j!=i && mn>dis[i][j]) mn=dis[i][j], ind=j;
        g[i].PB({ind, mn}), g[ind].PB({i, mn});
    }
    rel=location, res=stype;
    rel[0]=first, res[0]=1;
    dfs(0);
    while(count!=n){
        int mn=INF, ind=-1, type=-1, coord=-1;
        forn(i, n) if(!vis[i]) forn(j, 2){
            if(mn>dis[le[j]][i]) mn=dis[le[j]][i], type=j^1, coord=rel[le[j]]+(j? -mn : mn), ind=i;
            if(mn>dis[ri[j]][i]) mn=dis[ri[j]][i], type=j^1, coord=rel[ri[j]]+(j? -mn : mn), ind=i;
        }
        rel[ind]=coord, stype[ind]=type+1;
        if(rel[le[type]]>rel[ind]) le[type]=ind;
        if(rel[ri[type]]<rel[ind]) ri[type]=ind;
        dfs(ind);
    }
}

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