oj.uz

Submission #757827

# Submission time Handle Problem Language Result Execution time Memory
757827 2023-06-13T19:09:28 Z taher KOVANICE (COI15_kovanice) C++17
100 / 100
 636 ms 110896 KB 
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p , sz;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n); sz.resize(n);
    iota(p.begin(), p.end(), 0);
    fill(sz.begin() , sz.end() , 1);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      if(sz[y] < sz[x]) swap(x , y);
      p[x] = y;
      sz[y] += sz[x];
      return true;
    }
    return false;
  }
};

struct Node {
  int from , to;
  char eq;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n , m , v;
  cin >> n >> m >> v;
  vector<string> a(v);
  for (int i = 0 ; i < v ; i++) {
    cin >> a[i];
  }
  auto GetS = [&](string cur) {
    string t = "";    
    Node res;
    for (int i = 0 ; i < (int) cur.length() ; i++) {
      if (cur[i] >= '0' && cur[i] <= '9') {
        t.push_back(cur[i]);
      }
      else {
        res.from = stoi(t) - 1;
        res.eq = cur[i];
        t.clear();        
      }
    }
    res.to = stoi(t) - 1;
    return res;
  };
  vector<Node> all(v);
  for (int i = 0 ; i < v ; i++) {
    all[i] = GetS(a[i]);
  }
  dsu P(m);
  for (int i = 0 ; i < v ; i++) {
    if (all[i].eq == '=') {
      P.unite(all[i].from , all[i].to);
    }
  }
  vector<vector<int>> comps(m);
  for (int i = 0 ; i < m ; i++) {
    comps[P.get(i)].push_back(i);
  }
  vector<vector<vector<int>>> adj(m , vector<vector<int>> (2));
  vector<vector<int>> deg(m , vector<int> (2));
  for (int i = 0 ; i < v ; i++) {
    if (all[i].eq == '=') continue;
    int from = P.get(all[i].from);
    int to = P.get(all[i].to);
    adj[from][0].push_back(to);
    adj[to][1].push_back(from);
    deg[to][0] += 1;
    deg[from][1] += 1;
  }
  vector<vector<int>> pe(m , vector<int> (2 , -1));
  vector<int> tot;
  auto Process = [&](int t) {
    queue<int> que;
    for (int i = 0 ; i < m ; i++) {
      if (deg[i][t] == 0) {
        que.emplace(i);
        tot.emplace_back(i);
        pe[i][t] = 0;
      }
    }
    while (!que.empty()) {
      auto u = que.front();
      que.pop();
      for (auto id : adj[u][t]) {
        if (--deg[id][t] == 0) {
          que.push(id);
          tot.emplace_back(id);
          pe[id][t] = pe[u][t] + 1;
        }
      }
    }
    return ;
  };
  Process(0);
  Process(1);
  vector<int> res(m , -1);
  for (int i = 0 ; i < m ; i++) {
    if (pe[i][0] + pe[i][1] == n - 1) {
      res[i] = pe[i][0];
    }
  }
  for (int i = 0 ; i < m ; i++) {
    int u = P.get(i);
    if (res[u] == -1) {
      cout << "?\n";
    } else {
      cout << "K" << res[u] + 1 << '\n';
    }
  }
  return 0; 
}

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 62336 KB Output is correct
2 Correct 186 ms 62672 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6740 KB Output is correct
2 Correct 25 ms 6788 KB Output is correct
3 Correct 24 ms 6776 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 104404 KB Output is correct
2 Correct 480 ms 103824 KB Output is correct
3 Correct 474 ms 103880 KB Output is correct
4 Correct 636 ms 110264 KB Output is correct
5 Correct 630 ms 110896 KB Output is correct