Submission #846153

#	Time	Username	Problem	Language	Result	Execution time	Memory
846153		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	339 ms	37684 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
struct disjoint_sets {
  int N;
  vector<int> leader, rank;
  disjoint_sets(int n) : N(n) {
    leader.resize(N);
    rank.resize(N, 1);
    iota(leader.begin(), leader.end(), 0);
  }
  int get(int x) {
    return leader[x] = (x == leader[x] ? x : get(leader[x]));
  }
  bool unite(int x, int y) {
    x = get(x); 
    y = get(y);
    if (x == y) {
      return false;
    }   
    if (rank[x] < rank[y]) {
      swap(x, y);
    }
    leader[y] = x;
    rank[x] += rank[y];
    rank[y] = 0;
    return true; 
  }
  bool same(int x, int y) {
    return get(x) == get(y);
  }      
};
int main() {
  int N, M, V;
  cin >> N >> M >> V;
  disjoint_sets dsu(M);
  vector<array<int, 2>> E;
  for (int i = 0;i < V; ++i) {
    int u, v;
    char c;
    cin >> u >> c >> v;
    --u, --v;
    if (c == '=') {
      dsu.unite(u, v); 
    } else {
      E.push_back({u, v});
    }
  }
  vector<vector<int>> in(M), out(M);
  for (int i = 0;i < E.size(); ++i) {
    int u = dsu.get(E[i][0]);
    int v = dsu.get(E[i][1]);
    E[i] = {u, v};
    in[v].push_back(u);
    out[u].push_back(v);
  } 
  vector<vector<int>> dp(2, vector<int>(M, -1));
  function<int(int, int)> dfs = [&](int u, int t) {
    if (dp[t][u] != -1) {
      return dp[t][u];  
    }
    int go = 0;
    for (int v : (t ? out[u] : in[u])) {
      go = max(go, dfs(v, t) + 1);
    }  
    return dp[t][u] = go;
  };
  vector<int> ans(M);
  for (int i = 0;i < M; ++i) {
    int u = dsu.get(i);
    if (in[u].size() == 0) {
      dfs(u, 1); 
    }
    if (out[u].size() == 0) {
      dfs(u, 0);
    }
  } 
  for (int i = 0;i < M; ++i) {
    int u = dsu.get(i);
    if (dp[0][u] + dp[1][u] + 1 == N) {
      ans[u] = dp[0][u] + 1;
    }
    if (ans[u] == 0) {
      cout << "?\n";
      continue;
    }
    cout << "K" << ans[u] << '\n';
  }
}

Compilation message (stderr)

kovanice.cpp: In function 'int main()':
kovanice.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 0;i < E.size(); ++i) {
      |                  ~~^~~~~~~~~~

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