Submission #1309381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309381		ayaz	KOVANICE (COI15_kovanice)	C++20	0 / 100	2099 ms	60960 KiB

kovanice

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

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], g2[sz], g3[sz];
bool used[sz], ok;

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);
  }
};
int n, mx;
void dfs(int v) {
  used[v] = 1;
  for (auto u : g2[v]) {
    u = id[u];
    if (used[u]) continue;
    dfs(u);
  }
}
int m;
pii bfs(int s) {
  vi dep(m + 1, inf);
  queue<int> q;
  s = id[s];
  q.push(s);
  dep[s] = 0;
  int mxNode = q.front();
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto u : g[v]) {
      u = id[u];
      if (dep[u] != inf) continue;
      dep[u] = dep[v] + 1;
      q.push(u);
      if (dep[mxNode] < dep[u]) {
        mxNode = u;
      }
    }
  }
  return {mxNode, dep[mxNode]};
}
void dfsAns(int u) {
  if (ans[u] == -1) return;
  for (auto v : g[u]) {
    v = id[v];
    if (ans[v] != -1) continue;
    ans[v] = ans[u] + 1;
    dfsAns(v);
  }
}
int dfsAns2(int u) {
  if (ans[u] != -1) return ans[u];
  for (auto v : g[u]) {
    v = id[v];
    ans[u] = dfsAns2(v) - 1;
  }
  return ans[u];
}
pii bfs2(int s) {
  vi dep(m + 1, inf);
  queue<int> q;
  s = id[s];
  q.push(s);
  dep[s] = 0;
  int mxNode = q.front();
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto u : g3[v]) {
      u = id[u];
      if (dep[u] != inf) continue;
      dep[u] = dep[v] + 1;
      q.push(u);
      if (dep[mxNode] < dep[u]) {
        mxNode = u;
      }
    }
  }
  return {mxNode, dep[mxNode]};
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  // freopen("err.log", "w", stderr);
#endif
  precompute();
  int 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[u]]++;
    g[id[u]].emplace_back(id[v]);
    
    g2[id[v]].emplace_back(id[u]);
    g2[id[u]].emplace_back(id[v]);

    g3[id[v]].emplace_back(id[u]);
  }
  for (int i = 1; i <= m; i++) {
    int u = id[i];
    if (used[u]) continue;
    dfs(u);
    auto [x, X] = bfs(u);
    auto [_, y] = bfs2(x);
    debug(y);
    if (y != n - 1) continue;
    queue<int> q;
    q.push(_);
    ans[_] = 1;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (auto to : g[v]) {
        to = id[to];
        if (ans[to] != -1) continue;
        q.push(to);
        ans[to] = ans[v] + 1;
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    int u = id[i];
    dfsAns(u);
  }
  for (int i = 1; i <= m; i++) {
    int u = id[i];
    dfsAns2(u);
  }
  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: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40