Submission #755369

#	Time	Username	Problem	Language	Result	Execution time	Memory
755369		AngusRitossa	Rail (IOI14_rail)	C++14	30 / 100	382 ms	262148 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[5010];
struct UF
{
  int rep[5010];
  UF()
  {
    for (int i = 0; i < 5010; i++) rep[i] = i;
  }
  int findrep(int a)
  {
    if (rep[a] == a) return a;
    return rep[a] = findrep(rep[a]);
  }
  void merge(int a, int b)
  {
    rep[findrep(a)] = findrep(b);
  }
};
UF uf;
int ty[5010];
int seen[5010];
int loc[5010];
int dis[5010][5010];
void dfs(int a, int d, int type = 0)
{
  if (seen[a]) return;
  seen[a] = 1;
  ty[a] = type;
  loc[a] = d;
  for (int b : adj[a])
  {
    int newd = d;
    if (type) newd -= dis[a][b];
    else newd += dis[a][b];
    dfs(b, newd, !type);
  }
}
void findLocation(int n, int first, int location[], int stype[])
{
  vector<pair<int, pair<int, int> > > edges;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < i; j++)
    {
      int d = getDistance(i, j);
      edges.emplace_back(d, make_pair(i, j));
      dis[i][j] = dis[j][i] = d;
    }
  }
  sort(edges.begin(), edges.end());
  for (auto a : edges)
  {
    int u = a.second.first;
    int v = a.second.second;
    if (uf.findrep(u) != uf.findrep(v))
    {
      uf.merge(u, v);
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
  }
  dfs(0, first);
  for (int i = 0; i < n; i++) stype[i] = ty[i]+1;
  for (int i = 0; i < n; i++) location[i] = loc[i];
}

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