Submission #1309289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309289		ayaz	KOVANICE (COI15_kovanice)	C++20	50 / 100	142 ms	36376 KiB

kovanice

// We were born for this
#include <array>
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define line() "author : AyazN";
#endif

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define int ll

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int sz = 300500, inf = 1000000000, LOG = 30;
const ll mod = 1000000007, INF = 1000000000000000000;

int ans[sz], dep[sz], out[sz], in[sz];
vi g[sz];
bool used[sz], used2[sz];

void dfs(int v) {
  assert(!used[v]);
  used[v] = 1;
  for (auto &u : g[v]) {
    if (used[u]) continue;
    dep[u] = dep[v] + 1;
    dfs(u);
  }
}
int mx, col;
void dfsMax(int v) {
  used[v] = 1;
  mx = max(mx, ans[v]);
  for (auto &u : g[v]) {
    if (used[u]) continue;
    dfsMax(u);
  }
}
void dfsAns(int v) {
  used2[v] = 1;
  ans[v] = col;
  for (auto &u : g[v]) {
    if (used2[u]) continue;
    dfsAns(u);
  }
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  // freopen("err.log", "w", stderr);
#endif
  precompute();
  int n, m, v;
  cin >> n >> m >> v;
  for (int i = 1; i <= m; i++) {
    ans[i] = -1;
  }
  vpii edges;
  vector<array<int, 3>> op;
  for (int i = 1; i <= v; i++) {
    int a, b;
    char c;
    cin >> a >> c >> b;
    op.push_back({a, b, int(c)});
    if (c == '=') continue;
    edges.emplace_back(a, b);
    g[b].emplace_back(a);
    out[b]++;
    in[a]++;
  }
  for (int i = 1; i <= m; i++) {
    if (in[i] || used[i]) {
      continue;
    }
    dep[i] = 1;
    dfs(i);
  }
  queue<int> q;
  for (int i = 1; i <= m; i++) {
    if (dep[i] == n && out[i] == 0) {
      q.push(i);
      ans[i] = 1;
    }
    g[i].clear();
  }
  for (auto [u, v] : edges)
    g[u].emplace_back(v);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto &u : g[v]) {
      if (ans[u] == -1) {
        q.push(u);
        ans[u] = ans[v] + 1;
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    g[i].clear();
  }
  for (auto [u, v, _] : op) {
    if (char(_) != '=') continue;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  for (int i = 1; i <= m; i++) {
    used[i] = 0;
    used2[i] = 0;
  }
  for (int i = 1; i <= m; i++) {
    if (used[i]) continue;
    mx = -1;
    dfsMax(i);
    if (mx == -1) continue;
    col = mx;
    dfsAns(i);
  }
  for (auto [u, v, _] : op) {
    if (char(_) == '=') {
      // assert(ans[u] == ans[v]);
    } else {
      assert(ans[u] < ans[v]);
    }
  }
  for (int i = 1; i <= m; i++) {
    if (ans[i] == -1) {
      cout << "?\n";
    } else {
      cout << "K" << ans[i] << '\n';
    }
  }
}

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