oj.uz

Submission #1081781

# Submission time Handle Problem Language Result Execution time Memory
1081781 2024-08-30T10:35:21 Z juicy KOVANICE (COI15_kovanice) C++17
100 / 100
 101 ms 37044 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5 + 5;

int n, m, v;
int lab[N], a[N], b[N];
bool vis[N];
string res[N];
vector<int> g[N];

int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void mrg(int u, int v) {
  if ((u = find(u)) == (v = find(v))) {
    return;
  }
  if (lab[u] > lab[v]) {
    swap(u, v);
  }
  lab[u] += lab[v];
  lab[v] = u;
  return;
}

int get(string s) {
  int x = 0;
  for (auto c : s) {
    x = x * 10 + c - '0';
  }
  return x;
}

vector<int> ts;

void dfs(int u) {
  vis[u] = 1;
  for (int v : g[u]) {
    if (!vis[v]) {
      dfs(v);
    }
  }
  ts.push_back(u);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> v;
  vector<array<int, 2>> edges;
  fill(lab + 1, lab + m + 1, -1);
  while (v--) {
    string msg; cin >> msg;
    int sz = msg.size();
    for (int i = 0; i < sz; ++i) {
      if (!('0' <= msg[i] && msg[i] <= '9')) {
        int a = get(string(msg.begin(), msg.begin() + i));
        int b = get(string(msg.begin() + i + 1, msg.begin() + sz));
        if (msg[i] == '=') {
          mrg(a, b);
        } else {
          if (msg[i] == '>') {
            swap(a, b);
          }
          edges.push_back({a, b});
        }
        break;
      }
    }
  }
  for (auto [u, v] : edges) {
    g[find(u)].push_back(find(v));
  }
  for (int i = 1; i <= m; ++i) {
    if (find(i) == i && !vis[i]) {
      dfs(i);
    }
  }
  for (int u : ts) {
    for (int v : g[u]) {
      a[u] = max(a[u], a[v] + 1);
    }
  }
  reverse(ts.begin(), ts.end());
  for (int u : ts) {
    for (int v : g[u]) {
      b[v] = max(b[v], b[u] + 1);
    }
  }
  for (int i = 1; i <= m; ++i) {
    if (a[i] + b[i] == n - 1) {
      res[i] = "K" + to_string(b[i] + 1);
    } else {
      res[i] = "?";
    }
  }
  for (int i = 1; i <= m; ++i) {
    cout << res[find(i)] << "\n";
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16732 KB Output is correct
2 Correct 8 ms 16988 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 23480 KB Output is correct
2 Correct 43 ms 23628 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 18904 KB Output is correct
2 Correct 16 ms 18916 KB Output is correct
3 Correct 15 ms 18904 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 32968 KB Output is correct
2 Correct 86 ms 32264 KB Output is correct
3 Correct 82 ms 32196 KB Output is correct
4 Correct 87 ms 36288 KB Output is correct
5 Correct 94 ms 37044 KB Output is correct