제출 #1318681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318681		ayaz	KOVANICE (COI15_kovanice)	C++20	50 / 100	148 ms	24892 KiB

kovanice

// Pain
#include <bits/stdc++.h>
/*

  What we should do :
  1. L = Find longest path in each component
  2. L should be exactly n
  3. Then ans[u] = dep[u]
*/
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define vi vector<int>
#define vvi vector<vi>
#define eb emplace_back
#define pb push_back
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define isz(v) (int)v.size()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<bool> used;
vector<vector<pair<int, int>>> g;
vector<int> ans, dep, nodes, id, topo;
void dfs(int u) {
  u = id[u];
  used[u] = 1;
  for (auto [v, w] : g[u]) {
    v = id[v];
    if (!used[v]) dfs(v);
  }
  topo.push_back(u);
}
void makeDep(int u) {
  topo.clear();
  dfs(u);
  reverse(all(topo));
  for (auto u : topo) {
    u = id[u];
    if (dep[u] == 1e9) dep[u] = 0;
    for (auto [v, w] : g[u]) {
      w *= -1;
      v = id[v];
      dep[v] = min(dep[v], dep[u] + w);
    }
  }   
}
int mx;
void dfs2(int u) {
  u = id[u];
  used[u] = 1;
  nodes.push_back(u);
  mx = max(mx, -dep[u]);
  for (auto [v, w] : g[u]) {
    v = id[v];
    if (!used[v]) dfs2(v);
  }
}
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 (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
  }
  bool same(int x, int y) {
    return getpar(x) == getpar(y);
  }
};

int main() {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr);
  int n, m, v;
  cin >> n >> m >> v;
  g.resize(m + 1);
  used.resize(m + 1);
  ans.resize(m + 1, -1);
  id.resize(m + 1);
  dep.resize(m + 1, 1e9);
  DSU d;
  d.init(m);
  vector<pair<int, int>> ed;
  for (int i = 1; i <= v; i++) {
    int a, c; char b;
    cin >> a >> b >> c;
    if (b != '=')
      ed.push_back({a, c});
    else {
      d.connect(a, c);
    }
  }
  for (int u = 1; u <= m; u++) {
    id[u] = d.getpar(u);
  }
  for (auto [x, y] : ed) {
    x = id[x];
    y = id[y];
    g[x].push_back({y, 1});
  }
  for (int u = 1; u <= m; u++) {
    if (used[id[u]]) continue;
    makeDep(id[u]);
  }
  for (auto [x, y] : ed) {
    x = id[x];
    y = id[y];
    g[y].push_back({x, 1});
  }
  fill(all(used), 0);
  for (int u = 1; u <= m; u++) {
    if (used[id[u]]) continue;
    mx = -1e9;
    dfs2(id[u]);
    if (mx == n - 1) {
      for (auto &v : nodes) ans[id[v]] = -dep[id[v]] + 1;
    }
    nodes.clear();
  }
  for (int u = 1; u <= m; u++) {
    if (ans[id[u]] == -1) {
      cout << "?\n";
    } else {
      cout << "K" << ans[id[u]] << '\n';
    }
  }
  return 0;
}

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