Submission #958184

#	Time	Username	Problem	Language	Result	Execution time	Memory
958184		12345678	Rail (IOI14_rail)	C++17	30 / 100	52 ms	20564 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());
    if (!a.empty()) lst=a[0].second, stype[lst]=2, location[lst]=first+a[0].first;
    for (int i=1; i<a.size(); i++)
    {
        if (query(lst, a[i].second)+query(0, lst)==query(0, a[i].second)) location[a[i].second]=location[lst]-query(lst, a[i].second), stype[a[i].second]=1;
        else lst=a[i].second, location[lst]=first+query(0, lst), stype[lst]=2;
    }
    sort(b.begin(), b.end());
    if (!b.empty()) lst=b[0].second, stype[lst]=1, location[lst]=location[mn.second]-b[0].first;
    for (int i=1; i<b.size(); i++)
    {
        if (query(lst, b[i].second)+query(mn.second, lst)==query(mn.second, b[i].second)) location[b[i].second]=location[lst]+query(lst, b[i].second), stype[b[i].second]=2;
        else lst=b[i].second, location[lst]=location[mn.second]-query(mn.second, lst), stype[lst]=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:35: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]
   35 |     for (int i=1; i<a.size(); i++)
      |                   ~^~~~~~~~~
rail.cpp:42: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]
   42 |     for (int i=1; i<b.size(); i++)
      |                   ~^~~~~~~~~

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