Submission #399969

#	Time	Username	Problem	Language	Result	Execution time	Memory
399969		definitelynotmee	Rail (IOI14_rail)	C++98	30 / 100	401 ms	98668 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 0;

struct centro{
    int c, d;
};

int getDistance(int i, int j);

void findLocation(int n, int first, int location[], int stype[]){

    vector<vector<int>> dist(n,vector<int>(n,0));
    vector<pii> mini(n, {0,INF}); //first = indice mais proximo de i; second = distancia desse indice

    for(int i = 0; i < n; i++){
        location[i] = -1;
        for(int j = i+1; j < n; j++){
            dist[i][j] = getDistance(i,j);
            dist[j][i] = dist[i][j];
            if(dist[i][j] < mini[i].ss){
                mini[i] = {j,dist[i][j]};
            }
            if(dist[i][j] < mini[j].ss){
                mini[j] = {i,dist[i][j]};
            }
        }
    }
    vector<centro> v;
    for(int i = 0; i < n; i++){
        if(mini[i].ff > i){
            if(mini[mini[i].ff].ff == i)
                v.push_back({i, mini[i].ff});
        }
    }
    const int x = mini[0].ff;
    location[0] = first;
    location[x] = location[0] + dist[0][x];
    stype[0] = 1;
    stype[x] = 2;

    for(int i = 0; i < v.size(); i++){
        int lado = 0;
        if(min(dist[0][v[i].c],dist[0][v[i].d]) < min(dist[x][v[i].c],dist[x][v[i].d]))
            lado = 1; // lado é 1 se a menor distancia pra ele é o 0 e não o x
        if(lado){
            if(v[i].c != 0 && dist[0][v[i].c] < dist[0][v[i].d])
                swap(v[i].c, v[i].d);
            location[v[i].d] = location[0] + dist[0][v[i].d];
            location[v[i].c] = location[v[i].d] - dist[v[i].c][v[i].d];
        } else {
            if(v[i].d != x && dist[x][v[i].d] < dist[x][v[i].c])
                swap(v[i].d, v[i].c);
            location[v[i].c] = location[x] - dist[x][v[i].c];
            location[v[i].d] = location[v[i].c] + dist[v[i].c][v[i].d];
            
        }
        stype[v[i].c] = 1;
        stype[v[i].d] = 2;
    }
    for(int i = 0; i < n; i++){
        if(location[i] != -1){
            continue;
        }
        if(stype[mini[i].ff] == 1){
            location[i] = location[mini[i].ff] + mini[i].ss;
            stype[i] = 2;
        } else {
            location[i] = location[mini[i].ff] - mini[i].ss;
            stype[i] = 1;
        }
    }
}
/*int main(){
    int n;
    cin >> n;
    int location[n], stype[n];
    int first;
    cin >> first;
    findLocation(n,first,location,stype);
    for(int i = 0; i < n; i++){
        cout << location[i] << ' ';
    }
    cout << '\n';
    for(int i = 0; i < n; i++){
        cout << stype[i] << ' ';
    }
}*/

Compilation message (stderr)

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

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