Submission #493214

#	Time	Username	Problem	Language	Result	Execution time	Memory
493214		InternetPerson10	Rail (IOI14_rail)	C++17	30 / 100	78 ms	1476 KiB

rail

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

using namespace std;

vector<int> v0, vk;
vector<pair<int, int>> v1, v2;

map<pair<int, int>, int> MA;

int BIG = 1000001;

int ge(int x, int y) {
    pair<int, int> p = {min(x, y), max(x, y)};
    if(x == y) {
        MA[p] = 0;
    }
    else if(!MA.count(p)) MA[p] = getDistance(x, y);
    return MA[p];
}

void findLocation(int n, int first, int location[], int stype[]) {
    location[0] = first;
    stype[0] = 1;
    if(n == 1) return;
    v0.resize(n);
    vk.resize(n);
    for(int i = 0; i < n; i++) {
        v0[i] = ge(0, i); 
    }
    int mi = BIG;
    for(int i = 1; i < n; i++) {
        mi = min(mi, v0[i]);
    }
    int k = 1;
    for(int i = 1; i < n; i++) {
        if(mi == v0[i]) k = i;
    }
    location[k] = location[0] + mi;
    stype[k] = 2;
    for(int i = 0; i < n; i++) {
        if(i == 0 || i == k) continue;
        vk[i] = ge(i, k);
        int x = min(vk[i], v0[i]);
        if(x < mi) {
            location[i] = location[k] - x;
            stype[i] = 1;
        }
        else if(v0[i] == x) {
            v1.push_back({x, i});
        }
        else {
            v2.push_back({x, i});
        }
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    int la, g, h;
    if(v1.size()) {
        tie(h, la) = v1[0];
        location[la] = v1[0].first + location[0];
        stype[la] = 2;
        for(int i = 1; i < v1.size(); i++) {
            g = ge(v1[i].second, la);
            if(g <= abs(h - v1[i].first)) {
                location[v1[i].second] = location[la] - g;
                stype[v1[i].second] = 1;
            }
            else {
                location[v1[i].second] = v1[i].first + location[0];
                stype[v1[i].second] = 2;
                tie(h, la) = v1[i];
            }
        }
    }
    if(v2.size()) {
        tie(h, la) = v2[0];
        location[la] = location[k] - v2[0].first; 
        stype[la] = 1;
        for(int i = 1; i < v2.size(); i++) {
            g = ge(v2[i].second, la);
            if(g <= abs(h - v2[i].first)) {
                location[v2[i].second] = location[la] + g;
                stype[v2[i].second] = 2;
            }
            else {
                location[v2[i].second] = location[k] - v2[i].first;
                stype[v2[i].second] = 1;
                tie(h, la) = v2[i];
            }
        }
    }
    return;
}

Compilation message (stderr)

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

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