oj.uz

Submission #1120411

# Submission time Handle Problem Language Result Execution time Memory
1120411 2024-11-28T07:31:23 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 222 ms 52128 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F

const int MXN = 3e5 + 5;

int e[MXN];

int get(int x)
{
  if (e[x] < 0) return x;
  return e[x] = get(e[x]);
}
void unite(int x, int y)
{
  x = get(x), y = get(y);
  if (x == y) return;
  if (e[x] > e[y]) swap(x, y);
  e[x] += e[y];
  e[y] = x;
}

int n, m, k;
vector<int> adj[MXN], adjr[MXN];
vector<int> o;
int used[MXN];
int dp1[MXN], dp2[MXN];

void tp(int a)
{
  used[a] = 1;
  for (int &v : adj[a])
  {
    if (used[v]) continue;
    tp(v);
  }
  o.push_back(a);
}

signed main()
{
  scanf("%lld %lld %lld", &n, &m, &k);
  for (int i = 1; i <= m; i++) e[i] = -1;
  vector<array<int, 2>> ed;
  for (int i = 0; i < k; i++)
  {
    int u, v;
    char c;
    scanf("%lld%c%lld", &u, &c, &v);
    if (c == '<') ed.push_back({u, v});
    else if (c == '>') ed.push_back({v, u});
    else unite(u, v);
  }
  for (array<int, 2> &e : ed) if (get(e[0]) != get(e[1])) adj[get(e[0])].push_back(get(e[1])), adjr[get(e[1])].push_back(get(e[0]));
  for (int i = 1; i <= m; i++)
  {
    if (i == get(i) && !used[i]) tp(i);
  }
  for (int &i : o)
  {
    dp2[i] = max(dp2[i], 1LL);
    for (int &j : adjr[i]) dp2[j] = max(dp2[j], dp2[i] + 1);
  }
  reverse(o.begin(), o.end());
  for (int &i : o)
  {
    dp1[i] = max(dp1[i], 1LL);
    for (int &j : adj[i]) dp1[j] = max(dp1[j], dp1[i] + 1);
  }
  for (int i = 1; i <= m; i++)
  {
    if (dp1[get(i)] + dp2[get(i)] != n + 1) cout << "?\n";
    else 
    {
      cout << 'K' << dp1[get(i)] << '\n';
    }
  }
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%lld %lld %lld", &n, &m, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kovanice.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%lld%c%lld", &u, &c, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14672 KB Output is correct
2 Correct 11 ms 14672 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 26300 KB Output is correct
2 Correct 83 ms 26424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 18112 KB Output is correct
2 Correct 27 ms 18992 KB Output is correct
3 Correct 31 ms 18844 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 40060 KB Output is correct
2 Correct 157 ms 43448 KB Output is correct
3 Correct 183 ms 43244 KB Output is correct
4 Correct 212 ms 51364 KB Output is correct
5 Correct 222 ms 52128 KB Output is correct