Submission #1120411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120411		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	222 ms	52128 KiB

kovanice

#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40