Submission #1081784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081784		juicy	KOVANICE (COI15_kovanice)	C++17	100 / 100	117 ms	33008 KiB

kovanice

#include <bits/stdc++.h>

using namespace std;

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

const int N = 3e5 + 5;

int n, m, v;
int lab[N], a[N], b[N];
bool vis[N];
string res[N];
vector<int> g[N];

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

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

vector<int> ts;

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

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

  cin >> n >> m >> v;
  vector<array<int, 2>> edges;
  fill(lab + 1, lab + m + 1, -1);
  while (v--) {
    int a, b; char c;
    cin >> a >> c >> b;
    if (c == '=') {
      mrg(a, b);
    } else {
      if (c == '>') {
        swap(a, b);
      }
      edges.push_back({a, b});
    }
  }
  for (auto [u, v] : edges) {
    g[find(u)].push_back(find(v));
  }
  for (int i = 1; i <= m; ++i) {
    if (find(i) == i && !vis[i]) {
      dfs(i);
    }
  }
  for (int u : ts) {
    for (int v : g[u]) {
      a[u] = max(a[u], a[v] + 1);
    }
  }
  reverse(ts.begin(), ts.end());
  for (int u : ts) {
    for (int v : g[u]) {
      b[v] = max(b[v], b[u] + 1);
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (a[i] + b[i] == n - 1) {
      res[i] = "K" + to_string(b[i] + 1);
    } else {
      res[i] = "?";
    }
  }
  for (int i = 1; i <= m; ++i) {
    cout << res[find(i)] << "\n";
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40