제출 #1153279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153279		alexdd	철로 (IOI14_rail)	C++20	8 / 100	3103 ms	170272 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mp;
const int INF = 1e9;
int getd(int x, int y)
{
    if(x==y)
        return 0;
    if(x<0 || y<0)
        return INF;
    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();
    location[0] = first;
    stype[0] = 1;
    int le=0,ri=-1;
    while(1)
    {
        int ble=-1,bri=-1;
        for(int i=0;i<N;i++)
        {
            if(stype[i]!=0)
                continue;
            if(ble==-1 || getd(le,i) < getd(le,ble))
                ble = i;
            if(bri==-1 || getd(ri,i) < getd(ri,bri))
                bri = i;
        }
        if(ble==-1)
            break;
        if(getd(le,ble) < getd(ri,bri))
        {
            stype[ble] = 2;
            location[ble] = location[le] + getd(le,ble);

            for(int i=0;i<N;i++)
            {
                if(stype[i]!=0)
                    continue;
                if(getd(le,i) == getd(le,ble) + getd(ble,i) && getd(ble,i) < getd(le,ble) - getd(le,ri))
                {
                    stype[i] = 1;
                    location[i] = location[ble] - getd(ble,i);
                }
            }

            ri = ble;
        }
        else
        {
            stype[bri] = 1;
            location[bri] = location[ri] - getd(ri,bri);

            for(int i=0;i<N;i++)
            {
                if(stype[i]!=0)
                    continue;
                if(getd(ri,i) == getd(ri,bri) + getd(bri,i) && getd(bri,i) < getd(ri,bri) - getd(le,ri))
                {
                    stype[i] = 2;
                    location[i] = location[bri] + getd(bri,i);
                }
            }

            le = bri;
        }
    }
    //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";
}
/*

..(..(.......)............).....
     le      ri


*/

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