Submission #967132

#	Time	Username	Problem	Language	Result	Execution time	Memory
967132		nguyentunglam	Keys (IOI21_keys)	C++17	37 / 100	3055 ms	32700 KiB

keys

#include <vector>
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

bool vis_room[N], vis_key[N];

vector<pair<int, int> > e[N], adj[N];

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
  int n = r.size();
	vector<int> ans(n), p(n);
  for(int i = 0; i < U.size(); i++) {
    e[C[i]].emplace_back(U[i], V[i]);
    e[C[i]].emplace_back(V[i], U[i]);
    adj[U[i]].emplace_back(V[i], C[i]);
    adj[V[i]].emplace_back(U[i], C[i]);
  }
	for(int i = 0; i < n; i++) {
    queue<int> q_key, q_room;
    for(int j = 0; j < n; j++) vis_room[j] = vis_key[j] = 0;
    q_room.push(i);
    while (!q_key.empty() || !q_room.empty()) {
      if (!q_key.empty()) {
        int x = q_key.front(); q_key.pop();
        for(auto &[u, v] : e[x]) if (vis_room[u] || vis_room[v]) {
          if (!vis_room[u]) q_room.push(u), vis_room[u] = 1;
          if (!vis_room[v]) q_room.push(v), vis_room[v] = 1;
        }
      }
      if (!q_room.empty()) {
        p[i]++;
        int u = q_room.front(); q_room.pop();
        if (!vis_key[r[u]]) {
          vis_key[r[u]] = 1;
          q_key.push(r[u]);
        }
        for(auto &[v, c] : adj[u]) if (vis_key[c] && !vis_room[v]) {
          vis_room[v] = 1;
          q_room.push(v);
        }
      }
    }
	}

//	for(int i = 0; i < n; i++) cout << p[i] << " "; cout << endl;

	int mn = 1e9;

	for(int i = 0; i < n; i++) mn = min(mn, p[i]);

  for(int i = 0; i < n; i++) ans[i] = p[i] == mn;

	return ans;
}

#ifdef ngu
int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
    int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    std::vector<int> r(n), u(m), v(m), c(m);
    for(int i=0; i<n; i++) {
        assert(1 == scanf("%d", &r[i]));
    }
    for(int i=0; i<m; i++) {
        assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
    }
    fclose(stdin);

    std::vector<int> ans = find_reachable(r, u, v, c);

    for (int i = 0; i < (int) ans.size(); ++i) {
        if(i) putchar(' ');
        putchar(ans[i]+'0');
    }
    printf("\n");
    return 0;
}
#endif // ngu

Compilation message (stderr)

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

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33