Submission #792871

#	Time	Username	Problem	Language	Result	Execution time	Memory
792871		Ronin13	Rail (IOI14_rail)	C++17	56 / 100	1074 ms	98384 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

void findLocation(int N, int first, int location[], int stype[])
{
    location[0] = first;
    stype[0] = 1; 
    if(N == 1)
    return;
    int n= N;
    int d[n][n];
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            d[i][j] = d[j][i] = getDistance(i, j);
        }
    }
    bool good[n];
    fill(good, good + n, true);
    good[0] = false;
    for(int i = 1; i < n; i++){
        for(int j = 1; j < n; j++){
            if(j != i){
                if(d[0][i] == d[0][j] + d[j][i]) good[i] = false;
            }
        }
    }
    int mn = 1e9, mni;
    for(int i = 1; i < n; i++){
        if(mn > d[0][i])
             mn = d[0][i], mni = i; 
    }
    //cout << mn << "\n";
    int last = mni;
    while(mni != -1){
        int x = mni;
       // cout << x << ' ';
        last = x;
       mn = 1e9;
       mni = -1;
        for(int i = 0; i < n; i++){
            if(!good[i]) continue;
          //  if(d[x][i] != d[x][y] + d[y][i]) continue;
            if(d[0][i] <= d[0][x]) continue;
            if(d[0][i] < mn)
                mn = d[0][i], mni = i;
        }
    }
    location[last] = location[0] + d[0][last];
    stype[last] = 2;
    mn = 1e9;
    mni = -1;
    for(int i = 0; i < n; i++){
        bool good = true;
        if(i == last) continue;
        for(int j = 0; j < n; j++){
            if(i == j || j == last) continue;
            if(d[last][i] == d[last][j] + d[j][i]) {
                good = false;
                continue;
            }
        }
      //  if(good) cout << i << ' ';
        if(good) stype[i] = 1, location[i] = location[last] - d[last][i];
        if(good && location[i] < mn) 
            mn = location[i], mni = i;
    }
    last = mni;
    //cout << last << ' ' << "\n";
    for(int i = 0; i < n; i++){
        bool good = true;
        if(i == last) continue;
        for(int j = 0; j < n; j++){
            if(i == j || j == last) continue;
            if(d[last][i] == d[last][j] + d[j][i]) {
                good = false;
                continue;
            }
        }
        if(good) stype[i] = 2, location[i] = location[last] + d[last][i];
    }
    
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:57:14: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     location[last] = location[0] + d[0][last];
      |              ^~~~

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