Submission #1016539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016539		simona1230	Rail (IOI14_rail)	C++17	30 / 100	209 ms	98472 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"
using namespace std;

int l[5001],t[5001];
int d[5001][5001];
int minn[5001],vr[5001];
int n,cntt,t1=0,t2;
void rec(int v)
{
    //cout<<v<<endl;
    cntt++;
    if(t[vr[v]]==0)
    {
        if(t[v]==1)
        {
            t[vr[v]]=2;
            if(v==0)t2=vr[v];
            l[vr[v]]=l[v]+minn[v];
        }
        else
        {
            t[vr[v]]=1;
            l[vr[v]]=l[v]-minn[v];
        }
        rec(vr[v]);
    }
    for(int i=0; i<n; i++)
    {
        if(t[i]||vr[i]!=v)continue;
        if(t[v]==1)
        {
            if(v==0)t2=i;
            l[i]=l[v]+d[v][i];
            t[i]=2;
        }
        else
        {
            l[i]=l[v]-d[v][i];
            t[i]=1;
        }
        rec(i);
    }
}

void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    for(int i=0; i<N; i++)
        minn[i]=1e9;
    for(int i=0; i<N; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            d[i][j]=d[j][i]=getDistance(i,j);
            //cout<<i<<" "<<j<<" "<<d[i][j]<<endl;
            if(d[i][j]<minn[i])
            {
                //cout<<j<<endl;
                minn[i]=d[i][j];
                vr[i]=j;
            }
            if(d[i][j]<minn[j])
            {
                minn[j]=d[i][j];
                vr[j]=i;
            }
        }
    }
    //    cout<<vr[i]<<" "<<minn[i]<<endl;

    l[0]=first;
    t[0]=1;
    rec(0);

    while(cntt!=n)
    {
        //cout<<t1<<" "<<t2<<endl;
        int v1=0,d1=1e9,v2=0,d2=1e9;
        for(int i=0; i<n; i++)
        {
            if(!t[i]&&d[i][t1]<d1)
            {
                d1=d[i][t1];
                v1=i;
            }
            if(!t[i]&&d[i][t2]<d2)
            {
                d2=d[i][t2];
                v2=i;
            }
        }

        if(v1==v2)
        {
            if(d1<d2)
            {
                l[v1]=l[t1]+d1;
                t[v1]=2;
                rec(v1);
            }
            if(d2<d1)
            {
                l[v2]=l[t2]-d2;
                t[v2]=1;
                rec(v2);
            }
        }

        if(v1!=v2&&d1!=1e9)
        {
            l[v1]=l[t1]+d1;
            t[v1]=2;
            rec(v1);
        }
        if(v1!=v2&&d2!=1e9)
        {
            l[v2]=l[t2]-d2;
            t[v2]=1;
            rec(v2);
        }
        //cout<<v1<<" "<<d1<<" "<<v2<<" "<<d2<<endl;
        if(d1==1e9&&d2==1e9)
            break;
    }

    for(int i=0; i<n; i++)
    {
        location[i]=l[i],stype[i]=t[i];
        //cout<<i<<" "<<vr[i]<<" "<<minn[i]<<endl;
    }
}

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