Submission #1082525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082525		juicy	Izlet (COI19_izlet)	C++17	100 / 100	496 ms	83284 KiB

izlet

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3000;

int n, m;
int c[N][N], pr[N], a[N], cnt[N];
bool vis[N], same[N][N];
vector<int> g[N];

void add(int u, int v) {
  g[u].push_back(v);
  g[v].push_back(u);
}

int find(int u) {
  return pr[u] < 0 ? u : pr[u] = find(pr[u]);
}

void mrg(int u, int v) {
  if ((u = find(u)) == (v = find(v))) {
    return;
  }
  if (pr[u] > pr[v]) {
    swap(u, v);
  }
  pr[u] += pr[v];
  pr[v] = u;
  add(u, v);
} 

int check(int s) {
  memset(cnt, 0, sizeof(cnt));
  int active = 0, res = -1;
  function<void(int, int)> dfs = [&](int u, int p) {
    active += cnt[a[u]]++ == 0;
    if (res == -1 && active != c[s][u]) {
      res = a[u];
    }
    for (int v : g[u]) {
      if (vis[v] && v != p) {
        dfs(v, u);
      }
    }
    active -= --cnt[a[u]] == 0;
  };
  dfs(s, s);
  return ~res ? res : ++m;
}

void dfs(int u) {
  a[u] = check(u);
  vis[u] = 1;
  for (int v : g[u]) {
    if (!vis[v]) {
      dfs(v);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int _; cin >> _ >> n;
  memset(pr, -1, sizeof(pr));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> c[i][j];
      if (c[i][j] == 1) {
        mrg(i, j);
      }
    }
  }
  vector<int> root;
  for (int i = 0; i < n; ++i) {
    if (i == find(i)) {
      root.push_back(i);
    }
  }
  int m = root.size();
  for (int i = 0; i < m; ++i) {
    for (int j = i + 1; j < m; ++j) {
      int u = root[i], v = root[j];
      if (c[u][v] == 2 && !same[u][v]) {
        vector<int> ver{u, v};
        for (int k = j + 1; k < m; ++k) {
          int x = root[k];
          if (c[u][x] == 2 && c[v][x] == 2) {
            ver.push_back(x);
          }
        }
        for (int k = 1; k < ver.size(); ++k) {
          for (int l = 0; l < k; ++l) {
            same[ver[k]][ver[l]] = 1;
            same[ver[l]][ver[k]] = 1;
          } 
          add(ver[0], ver[k]);
        }
      }
    }
  }
  dfs(0);
  for (int i = 0; i < n; ++i) {
    cout << a[find(i)] << " \n"[i + 1 == n];
  }
  for (int i = 0; i < n; ++i) {
    for (int j : g[i]) {
      if (i < j) {
        cout << i + 1 << " " << j + 1 << "\n";
      }
    }
  }
  return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int k = 1; k < ver.size(); ++k) {
      |                         ~~^~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57