Submission #783951

#	Time	Username	Problem	Language	Result	Execution time	Memory
783951		FatihSolak	Rail (IOI14_rail)	C++17	56 / 100	90 ms	98392 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int dp[5000][5000];
int tot = 0;
int get(int a,int b){
    if(a == b)
        return 0;
    if(dp[a][b] || dp[b][a])
        return max(dp[a][b],dp[b][a]);
    tot--;
    assert(tot >= 0);
    return dp[a][b] = getDistance(a,b);
}
void findLocation(int n, int first, int location[], int stype[]){
    tot = n * (n-1)/2;
    for(int i = 0;i<n;i++){
        stype[i] = 0;
        for(int j = 0;j<n;j++){
            dp[i][j] = 0;
        }
    }
    location[0] = first;
    stype[0] = 1;
    if(n == 1)return;
    vector<int> ord0;
    for(int i = 0;i<n;i++){
        if(i != 0){
            ord0.push_back(i);
        }
    }
    sort(ord0.begin(),ord0.end(),[&](int a,int b){
        return get(0,a) < get(0,b);
    });
    int posD = ord0[0];
    location[posD] = location[0] + get(0,posD);
    stype[posD] = 2;
    vector<int> v;
    v.push_back(0);
    for(int i = 1;i<ord0.size();i++){
        if(get(0,ord0[i]) != get(posD,ord0[i]) + get(0,posD))continue;
        if(get(posD,ord0[i]) < get(0,posD)){
            stype[ord0[i]] = 1;
            location[ord0[i]] = location[posD] - get(posD,ord0[i]);
            continue;
        }
        int candpos = location[v.back()] + get(v.back(),ord0[i]);
        int closest = -1;
        for(auto u:v){
            if(location[u] < candpos){
                if(closest == -1 || location[closest] < location[u]){
                    closest = u;
                }
            }
        }
        assert(closest != -1);
        if(get(posD,ord0[i]) != get(posD,closest) + get(closest,ord0[i])){
            v.push_back(ord0[i]);
            stype[ord0[i]] = 1;
            location[ord0[i]] = location[posD] - get(posD,ord0[i]);
        }
        else{
            stype[ord0[i]] = 2;
            location[ord0[i]] = candpos;
        }
    }
    // for(int i = 0;i<n;i++){
    //     if(stype[i]){
    //         cout << i << endl;
    //         cout << stype[i] << ' ' << location[i] << endl;
    //     }
    // }
    vector<int> ordD;
    for(int i = 0;i<n;i++){
        if(i != posD){
            ordD.push_back(i);
        }
    }
    sort(ordD.begin(),ordD.end(),[&](int a,int b){
        return get(posD,a) < get(posD,b);
    });
    v.clear();
    v.push_back(posD);
    for(int i = 1;i<ordD.size();i++){
        if(stype[ordD[i]])continue;
        int candpos = location[v.back()] - get(v.back(),ordD[i]);
        int closest = -1;
        for(auto u:v){
            if(location[u] > candpos){
                if(closest == -1 || location[closest] > location[u]){
                    closest = u;
                }
            }
        }
        assert(closest != -1);
        if(get(0,ordD[i]) != get(0,closest) + get(closest,ordD[i])){
            v.push_back(ordD[i]);
            stype[ordD[i]] = 2;
            location[ordD[i]] = location[0] + get(0,ordD[i]);
        }
        else{
            stype[ordD[i]] = 1;
            location[ordD[i]] = candpos;
        }
    }
    // for(int i = 0;i<n;i++){
    //     if(stype[i]){
    //         cout << i << endl;
    //         cout << stype[i] << ' ' << location[i] << endl;
    //     }
    // }
}

Compilation message (stderr)

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

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