Submission #958188

#	Time	Username	Problem	Language	Result	Execution time	Memory
958188		12345678	철로 (IOI14_rail)	C++17	56 / 100	548 ms	68008 KiB

rail

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

using namespace std;

const int nx=5e3+5;

int dp[nx][nx], lst;

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);
}

vector<pair<int, int>> a, b;

void findLocation(int N, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    pair<int, int> mn={INT_MAX, 0};
    for (int i=1; i<N; i++) mn=min(mn, {query(0, i), i});
    location[mn.second]=first+mn.first;
    stype[mn.second]=2;
    for (int i=1; i<N; i++)
    {
        if (i==mn.second) continue;
        if (query(0, mn.second)+query(mn.second, i)==query(0, i)) b.push_back({query(mn.second, i), i});
        else a.push_back({query(0, i), i});
    }
    sort(a.begin(), a.end());
    for (int i=0; i<a.size(); i++)
    {
        int loc;
        bool can=1;
        for (int j=0; j<i; j++) if (query(0, a[j].second)+query(a[j].second, a[i].second)==query(0, a[i].second)) can=0, loc=a[j].second;
        if (!can) location[a[i].second]=location[loc]-query(loc, a[i].second), stype[a[i].second]=1;
        else location[a[i].second]=first+query(0, a[i].second), stype[a[i].second]=2;
    }
    sort(b.begin(), b.end());
    for (int i=0; i<b.size(); i++)
    {
        int loc;
        bool can=1;
        for (int j=0; j<i; j++) if (query(mn.second, b[j].second)+query(b[j].second, b[i].second)==query(mn.second, b[i].second)) can=0, loc=b[j].second;
        if (!can) location[b[i].second]=location[loc]+query(loc, b[i].second), stype[b[i].second]=2;
        else location[b[i].second]=location[mn.second]-query(mn.second, b[i].second), stype[b[i].second]=1;
    }
    //for (int i=0; i<N; i++) cout<<"debug "<<i<<' '<<stype[i]<<' '<<location[i]<<'\n';
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0; i<a.size(); i++)
      |                   ~^~~~~~~~~
rail.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0; i<b.size(); i++)
      |                   ~^~~~~~~~~

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