제출 #1309364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309364		ayaz	KOVANICE (COI15_kovanice)	C++20	0 / 100	111 ms	39480 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], 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) {
  assert(!used[v]);
  used[v] = 1;
  mx = max(dep[v], mx);
  ok |= (dep[v] == n);
  for (auto u : g[v]) {
    u = id[u];
    if (used[u]) continue;
    dep[u] = dep[v] + 1;
    dfs(u);
  }
}
bool used2[sz];
void dfsAns(int u) {
  used2[u] = 1;
  ans[u] = n - dep[u] + 1;
  for (auto v : g[u]) {
    v = id[v];
    if (used2[v]) continue;
    dfsAns(v);
  }
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  // freopen("err.log", "w", stderr);
#endif
  precompute();
  int 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[u]]++;
    out[id[v]]++;
    g[id[v]].emplace_back(id[u]);
  }
  for (int i = 1; i <= m; i++) {
    int u = id[i];
    if (in[u] == 0 && !used[u]) {
      dep[u] = 1;
      ok = false;
      mx = 0;
      dfs(u);
      if (ok && mx <= n) {
        dfsAns(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