Submission #713572

#	Time	Username	Problem	Language	Result	Execution time	Memory
713572		lam	Rail (IOI14_rail)	C++14	100 / 100	195 ms	99212 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int d[maxn][maxn];
int n;
int a[maxn];
int ans[maxn];
inline int calc(int u, int v)
{
    if (u>v) swap(u,v);
    if (d[u][v] == -1) d[u][v] = getDistance(u,v);
    return d[u][v];
}
bool cmp(int x, int y)
{
    return calc(0,x)<calc(0,y);
}
void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    for (int i=0; i<n; i++) stype[i] = ans[i] = -1;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) d[i][j] = -1;
    ans[0] = first;
    for (int i=1; i<n; i++)
    {
        int temp = calc(0,i);
        a[i] = i;
    }
    ans[0] = first;
    sort(a+1,a+n,cmp);
    int L = 0; int R = a[1];
    ans[R] = ans[L] + calc(L,R);
    stype[R] = 1;
    stype[L] = 0;
    set<int> ll,rr;
    ll.insert(ans[L]); rr.insert(ans[R]);
    for (int i=2; i<n; i++)
    {
        int k = a[i];
        int x = calc(k,L); int y=calc(k,R);
        int canl = ans[L] + x; int canr = ans[R] - y;
        auto it = --ll.upper_bound(canl);
        int res;
        if (y == canl + ans[R] - 2*(*it)) res = 0;
        else
        {
            it = rr.upper_bound(canr);
            if (it!=rr.end()&&x == 2*(*it) - canr - ans[L]) res=1;
            else if (calc(0,k) == 2*ans[a[1]] - first - canr) res=1;
            else res=0;
        }
        cerr<<L<<' '<<R<<' '<<x<<' '<<y<<' '<<canl<<' '<<canr<<" = "<<res<<endl;
        if (res==0)
        {
            ans[k] = canl;
            rr.insert(canl);
            stype[k] = 1;
            if (ans[k] > ans[R]) R=k;
        }
        else
        {
            ans[k] = canr;
            ll.insert(canr);
            stype[k] = 0;
            if (ans[k] < ans[L]) L = k;
        }
    }
    for (int i=0; i<n; i++) stype[i] ++;
    ans[0] = first;
    for (int i=0; i<n; i++) location[i] = ans[i];
    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:29:13: warning: unused variable 'temp' [-Wunused-variable]
   29 |         int temp = calc(0,i);
      |             ^~~~

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