Submission #736692

#	Time	Username	Problem	Language	Result	Execution time	Memory
736692		cig32	Rail (IOI14_rail)	C++17	56 / 100	502 ms	98552 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;
int dsu[MAXN];

int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}
int importance[MAXN];
int opt[MAXN];
int type[MAXN];

void findLocation(int N, int first, int location[], int stype[])
{
  if(N == 1) {
    location[0] = first;
    stype[0] = 1;
    return;
  }
  int dist[N][N];
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      if(i == j) dist[i][j] = 0;
      else if(i > j) dist[i][j] = dist[j][i];
      else dist[i][j] = getDistance(i, j);
    }
  }
  for(int i=0; i<N; i++) dsu[i] = i;
  type[0] = 1, location[0] = first;
  for(int i=0; i<N; i++) {
    int mi = 1e9, id;
    for(int j=0; j<N; j++) {
      if(i != j && dist[i][j] < mi) mi = dist[i][j], id = j;
    }
    opt[i] = id;
    importance[id]++;
    union_(i, id);
  }
  int Lc, Rc;
  Rc = opt[0];
  Lc = opt[Rc];
  location[Rc] = location[0] + dist[0][Rc];
  location[Lc] = location[Rc] - dist[Lc][Rc];
  type[Lc] = 1;
  type[Rc] = 2;
  for(int i=0; i<N; i++) {
    vector<int> V;
    for(int j=0; j<N; j++) if(set_of(j) == i) V.push_back(j);
    if(V.empty()) continue;
    vector<int> W;
    int dir; // 0 left 1 right
    for(int x: V) {
      if(importance[x]) {
        W.push_back(x);
        if(dist[x][Lc] < dist[x][Rc]) dir = 1;
        else dir = 0;
      }
    }
    if(W[0] == Lc || W[1] == Lc) continue;
    if(dir == 0) {
      if(dist[W[0]][Rc] < dist[W[1]][Rc]) type[W[0]] = 1, type[W[1]] = 2;
      else type[W[0]] = 2, type[W[1]] = 1;
    }
    else {
      if(dist[W[0]][Lc] < dist[W[1]][Lc]) type[W[0]] = 2, type[W[1]] = 1;
      else type[W[0]] = 1, type[W[1]] = 2;
    }
  }
  for(int i=0; i<N; i++) type[i] = 3 - type[opt[i]];
  for(int i=0; i<N; i++) {
    if(i == Lc || i == Rc) continue;
    if(dist[Lc][i] < dist[Rc][i]) {
      if(type[i] == 2) location[i] = location[Lc] + dist[Lc][i];
      else location[i] = location[Lc] + dist[Lc][i] - 2 * dist[i][opt[i]];
    }
    else {
      if(type[i] == 1) location[i] = location[Rc] - dist[Rc][i];
      else location[i] = location[Rc] - dist[Rc][i] + 2 * dist[i][opt[i]];
    }
  }
  for(int i=0; i<N; i++) stype[i] = type[i];
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:66:5: warning: 'dir' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     if(dir == 0) {
      |     ^~
rail.cpp:10:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   10 |   return dsu[u] = set_of(dsu[u]);
      |          ~~~~~~~^~~~~~~~~~~~~~~~
rail.cpp:37:19: note: 'id' was declared here
   37 |     int mi = 1e9, id;
      |                   ^~

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