Submission #846248

#	Time	Username	Problem	Language	Result	Execution time	Memory
846248		vjudge1	KOVANICE (COI15_kovanice)	C++17	10 / 100	2096 ms	82468 KiB

kovanice

// clang-format off
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define lg2(x) (63 - __builtin_clzll(x))
#define db cerr << "BREAK\n"
#define fp(...) fprintf(stderr, __VA_ARGS__)
#define rs(a) a.resize(n)
#define hizli cin.tie(0);ios_base::sync_with_stdio(0)
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(a, b) for (int a = 0; a < b; a++)
#define af(x) for(auto&a:x)fp("%d ",a);fp("\n")
#define ff first
#define ss second
#define job main
// clang-format on
template <typename... Args> void in(Args &&...args) {
  (std::cin >> ... >> args);
}
const int N = 2e5 + 5, MOD = 1e9 + 7;
/*
~Y .5. J~ ~J .5. 5: 77 :5  5: ?! ^Y ~J .5. Y^ ~? .5..Y^ !? .
^J .5. ?! ^J .5. Y: !7 :P^^G~.J7 ^Y ~J .5. Y^ ~J .5..Y^ 7? .
^Y .5. ?! ~J .5. Y^.Y##&&&@@&&&&G55 ^J .5. J~ ~? .5. Y~ !J .
^Y .5. J! ~J .5. 5#&@@@&&&@&@@@@@@&J!J .5. J~ ~J .5. Y^ !J .
:Y  5: ?! :Y .5^5&@@@@&&&&&&&@@@@&@@&5 .5. J~ ~J .5. Y~ ~Y .
:5  5: ?! ^Y  P&@&&&&&&&&&&&&&&&&&&&&&!.P. Y~ ^J .5. Y~ ~J..
.5. Y: 77 ^Y .B&&&&&&&&&&&&&&B5YYG&&&@&:5. J! ~Y .5. J~ ~J .
.5. Y^ 77 ^Y ?&&&&&&&&&&&B5J7!7??JP&&@@YY. ?! ~Y .5. Y~ ~Y .
.5  Y^ !7 ^Y J#BP5555B#G7~~~!!7?JY5B@@@P5: J! ~J .P. J~ ~J..
.5  5: 7? ^Y ~&#5J?7!7?!!77!!!!7?J5P#@@BG! Y! !Y .P. J~ ~J .
.5  Y^ !J :5 .G&PYJ77!!~~!!~~!!?JY5PG&&P5~ Y7 ~Y .P. J~ ~Y .
.5. Y^ !J :5  Y&#5J7777!!777JPGBBBGGPB&PY^ J7 ^5 .P: J~ ~Y..
.P. Y~ !Y .5  YG&GP55PGP5J?5#BPGGG5Y5G#55: ?7 :5..P: ?! ^5..
.5. J~ !Y :5. 5^5#GB#BBGP5!?5YJJ?7?J5GG55: ?? :P..P: ?7 ^P..
.P. J~ !Y :5. 5:.PPJYYYJ?Y!~?J?77!7J5GB#B: ?? :P..P: ?7 ^5.
.P. J! ~Y .P. 5^ !5Y?777?57^7JYJ??J5PBB&@G.7? :P..P: ?? :5..
.P. ?7 ^Y .P. 5^ 77^PJ??7Y5?YG5JJ5PPGB##&@&BJ :P..P: ?? :5.
 P: ?7 ^5 .P. Y^ 7J 7GYJ?JPGGP5PGGPGB#BB&@@@&J~P. 5^ 7J :P.
 5: ?7 :5 .P. Y~ 7PJB&BPPGGPP5PGGY5G##G&@@@&@@&&Y:5^ 7J :P.
 5: ?? :5 .P^:PGG&@@@@@&BG55PPPYJY5#&B#&&&&&&&&&@&&J.!? :P.
 5^ !J:!BYP#&&&&&@@@@@@@@&B5YYYYPG#&B#&&&&&&&@@&&&&&#B5..P.
 5~ Y&&&&&&&&&&&&&@@&@@@@@@####&&&&##&&&&&&&&@&&&&&&&&&#GB:
 Y!J&&&&&&&&&&&&&&&&&&@@@@@&##&&&&##&&&&&&&&&&&&&&&&&&&&&&#J
 ?J#&&&&&&&&&&&&&&&&&&&&@@@###&&&BB&&&&&&&&&&&&&&&&&&&&&&&&&
 ?B&&&&&&&&&&&&&&&&&&&&&&@@&BBBBGB&&&&&&&&&@@&&&&&&&&&&&&&&&
 ?&&&&&&&&&&&&&&&&&&&&&&&@@@&BGGB&&&&&&&&&@&&&&&&&&&&&&&&&&&
 J&&&&&&&&&&&&&&&&&&&&&&@@@@@@@@&&&&&&&&&&&&&&&&&&&&&&&&&&@@
 Y&&&&&&&&&&&&&&&&&&&&&&@@@@@@@@&&&&&&&&&&&&&&&&&&&&&&&&@&@@*/

vector<unordered_set<int>> adj;
vector<unordered_set<int>> adj2;
vector<int> val, vis;

int n, m, v;

bool dfs(int node, int depth = 1) {
  bool is = false;
  if (vis[node]) {
    return val[node];
  }
  if(val[node]){
    return val[node];
  }
  vis[node] = 1;
  for (auto &child : adj2[node]) {
    if (dfs(child, depth) && val[child] == depth ) {
      val[node] = depth;
      is = true;
    }
  }

  if (depth == n) {
    is = true;
    val[node] = depth;
    return is;
  }
  if (adj[node].empty()) {
    return is;
  }
  for (auto &child : adj[node]) {
    if (dfs(child, depth + 1) && val[child] == depth + 1) {
      val[node] = depth;
      is = true;
    }
  }
  return is;
}

int job() {
  hizli;
  in(n, m, v);
  adj.resize(m);
  adj2.resize(m);
  vis.resize(m);
  val.resize(m);
  for (int i = 0; i < v; i++) {
    int a, b;
    char c;
    in(a, c, b);
    a--, b--;
    if (c == '=') {
      adj2[a].insert(b);
      adj2[b].insert(a);
    } else if (c == '<') {
      adj[b].insert(a);
    } else {
      adj[a].insert(b);
    }
  }
  // for (auto &a : tobemerged) {
  //   adj[a.ff].merge(adj[a.ss]);
  //   adj[a.ss].merge(adj[a.ff]);
  // }
  for (int i = 0; i < m; i++) {
    vis = vector<int>(m,0);
    dfs(i);
  }
  for (int i = 0; i < m; i++) {
    vis = vector<int>(m,0);
    dfs(i);
  }
  for (auto &a : val) {
    if (a == 0) {
      cout << "?\n";
    } else {
      cout << "K" << n + 1 - a << endl;
    }
  }
}

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