oj.uz

Submission #21028

# Submission time Handle Problem Language Result Execution time Memory
21028 2017-03-30T07:52:51 Z model_code KOVANICE (COI15_kovanice) C++11
100 / 100
 413 ms 100280 KB 
// Autor: Gustav Matula 

#include <cstdio>
#include <cassert>
#include <cstring>

#include <algorithm>
#include <iostream>

using namespace std;
typedef long long llint;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

const int MAXN = 1000005;

int n, m, v;
vector< pair< int, int > > E;
vector< int > B[MAXN];
int com[MAXN];

void mark(int i, int c) {
  if (com[i]) return;
  com[i] = c;
  for (int j : B[i])
    mark(j, c);
}

vector< int > D[MAXN]; int d[MAXN];
vector< int > R[MAXN]; int r[MAXN];

int dfs(int i, vector< int > *D, int *d) {
  if (d[i] != 0) return d[i];
  for (int j : D[i]) d[i] = max(d[i], dfs(j, D, d));
  return ++d[i];
}

int main(void) 
{
  scanf("%d%d%d", &n, &m, &v);

  REP(i, v) {
    int a, b; char op;
    scanf("%d%c%d", &a, &op, &b);
    if (op == '<') 
      E.push_back({a, b});
    else {
      B[a].push_back(b);
      B[b].push_back(a);
    }
  }

  FOR(i, 1, m + 1) if (!com[i]) mark(i, i);

  for (auto e : E) {
    D[com[e.first]].push_back(com[e.second]);
    R[com[e.second]].push_back(com[e.first]);
  }

  FOR(i, 1, m + 1) dfs(com[i], D, d);
  FOR(i, 1, m + 1) dfs(com[i], R, r);

  FOR(i, 1, m + 1) {
    if (d[com[i]] + r[com[i]] - 1 == n)
      printf("K%d\n", r[com[i]]);
    else
      puts("?");
  }

  return 0;
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:43:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &m, &v);
                              ^
kovanice.cpp:47:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%c%d", &a, &op, &b);
                                 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 84188 KB Output is correct
2 Correct 16 ms 84188 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 89204 KB Output is correct
2 Correct 143 ms 89104 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 86384 KB Output is correct
2 Correct 59 ms 86376 KB Output is correct
3 Correct 49 ms 86372 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 98116 KB Output is correct
2 Correct 386 ms 97764 KB Output is correct
3 Correct 359 ms 97756 KB Output is correct
4 Correct 383 ms 100132 KB Output is correct
5 Correct 409 ms 100280 KB Output is correct