Submission #958159

#	Time	Username	Problem	Language	Result	Execution time	Memory
958159		12345678	Rail (IOI14_rail)	C++17	56 / 100	2181 ms	135372 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e3+5;

int dp[nx][nx], mn[nx], vs[nx];

int query(int i, int j)
{
    if (i>j) swap(i, j);
    if (dp[i][j]!=0) return dp[i][j];
    return dp[i][j]=getDistance(i, j);
}

void findLocation(int N, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 0});
    for (int i=1; i<N; i++) mn[i]=1e9; 
    while (!pq.empty())
    {
        auto [w, u]=pq.top();
        pq.pop();
        if (vs[u]) continue;
        vs[u]=1;
        for (int v=0; v<N; v++) if (v!=u&&mn[v]>query(u, v)) mn[v]=query(u, v), stype[v]=2-stype[u]+1, location[v]=(stype[u]==1)?location[u]+query(u, v):location[u]-query(u, v), pq.push({query(u, v), v});
    }
    //for (int i=0; i<N; i++) cout<<"debug "<<i<<' '<<stype[i]<<' '<<location[i]<<'\n';
}

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