Submission #1153068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153068		alexdd	Rail (IOI14_rail)	C++20	30 / 100	38 ms	1860 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mp;
int getd(int x, int y)
{
    if(x==y)
        return 0;
    if(x>y)
        swap(x,y);
    if(mp[{x,y}]==0)
        mp[{x,y}] = getDistance(x,y);
    return mp[{x,y}];
}
void findLocation(int N, int first, int location[], int stype[])
{
    mp.clear();
    if(N==1)
    {
        location[0] = first;
        stype[0] = 1;
        return;
    }
    int primu=1;
    for(int i=1;i<N;i++)
        if(getd(0,i) < getd(0,primu))
            primu = i;

    //cerr<<primu<<" "<<getd(0,primu)<<" primu\n";

    int le=0,mxm=getd(0,primu);
    for(int i=1;i<N;i++)
    {
        if(i==primu)
            continue;
        if(getd(0,i) == getd(0,primu) + getd(primu,i))
        {
            if(getd(primu,i) > mxm)
            {
                mxm = getd(primu,i);
                le = i;
            }
        }
    }
    //cerr<<le<<" le\n";

    location[le] = first + getd(0,primu) - getd(primu,le);
    stype[le] = 1;

    vector<pair<int,int>> dle;
    for(int i=0;i<N;i++)
        if(i!=le)
            dle.push_back({getd(le,i),i});
    sort(dle.begin(),dle.end());
    for(auto [_,i]:dle)
    {
        if(stype[i]!=0)
            continue;
        location[i] = location[le] + getd(le,i);
        stype[i] = 2;
        for(int j=0;j<N;j++)
        {
            if(stype[j]==0 && getd(le,j) == getd(le,i) + getd(i,j))
            {
                stype[j] = 1;
                location[j] = location[i] - getd(i,j);
            }
        }
    }
    assert(location[0]==first);
    //cerr<<"location: ";for(int i=0;i<N;i++) cerr<<location[i]<<" ";cerr<<"\n";
    //cerr<<"stype: ";for(int i=0;i<N;i++) cerr<<stype[i]<<" ";cerr<<"\n";
}

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