Submission #1309332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309332		ayaz	KOVANICE (COI15_kovanice)	C++20	50 / 100	132 ms	42044 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], out[sz], in[sz];
int id[sz], dep[sz];
vi g[sz];
bool used[sz], used2[sz];

struct DSU {
  vi p, sz;
  int n, compo;
  void init(int _n) {
    n = _n;
    compo = n;
    p.resize(n + 1);
    sz.resize(n + 1, 1);
    for (int i = 1; i <= n; i++) p[i] = i;
  }
  int getpar(int x) {
    if (p[x] != x) p[x] = getpar(p[x]);
    return p[x];
  }
  void connect(int x, int y) {
    int a = getpar(x);
    int b = getpar(y);
    if (a == b) return;
    if (out[a] == 0 && out[b]) std::swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
  }
  bool same(int x, int y) {
    return getpar(x) == getpar(y);
  }
};


void dfs(int v) {
  assert(!used[v]);
  used[v] = 1;
  debug(v);
  for (auto &u : g[v]) {
    u = id[u];
    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]) {
    u = id[u];
    if (used[u]) continue;
    dfsMax(u);
  }
}
void dfsAns(int v) {
  used2[v] = 1;
  ans[v] = col;
  for (auto &u : g[v]) {
    u = id[u];
    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;
  DSU d; d.init(m);
  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 == '=') {
      d.connect(a, b);
      continue;
    }
    edges.emplace_back(a, b);
  }
  for (int i = 1; i <= m; i++) {
    id[i] = d.getpar(i);
  }
  for (auto [u, v] : edges) {
    in[id[v]]++;
    out[id[u]]++;
    g[id[v]].emplace_back(id[u]);
  }
  for (int i = 1; i <= m; i++) {
    int u = id[i];
    if (out[u] || used[u]) {
      continue;
    }
    dep[u] = 1;
    dfs(u);
  }
  queue<int> q;
  for (int i = 1; i <= m; i++) {
    int u = id[i];
    if (dep[u] == n && in[u] == 0) {
      q.push(u);
      ans[u] = 1;
    }
    g[u].clear();
  }
  for (auto [u, v] : edges) {
    u = id[u];
    v = id[v];
    if (u == v) continue;
    g[u].emplace_back(v);
  }
  while (!q.empty()) {
    int v = q.front();
    v = id[v];
    q.pop();
    for (auto &u : g[v]) {
      u = id[u];
      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;
    u = id[u]; v = id[v];
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  for (int i = 1; i <= m; i++) {
    used[i] = 0;
    used2[i] = 0;
  }
  for (auto [u, v, _] : op) {
    if (char(_) == '=') {
      // assert(ans[u] == ans[v]);
    } else {
      if (ans[v] != -1)
        assert(ans[u] < ans[v]);
    }
  }
  for (int i = 1; i <= m; i++) {
    int u = id[i];
    if (ans[u] == -1) {
      cout << "?\n";
    } else {
      cout << "K" << ans[u] << '\n';
    }
  }
}

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