Submission #987151

#	Time	Username	Problem	Language	Result	Execution time	Memory
987151		cig32	Keys (IOI21_keys)	C++17	37 / 100	3019 ms	28732 KiB

keys

#include <vector>
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 3e5 + 10;

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();
  std::vector<int> ans(n);
  int m = u.size();
  vector<pair<int,int> > adj[n];
  for(int i=0; i<m; i++) {
    adj[u[i]].push_back({v[i], c[i]});
    adj[v[i]].push_back({u[i], c[i]});
  }

  
  int freq[n];
  int mn = 1e9;
  for(int i=0; i<n; i++) {
    bool key[n];
    vector<int> can[n];
    bool vis[n];
    for(int i=0; i<n; i++) key[i] = 0;
    for(int i=0; i<n; i++) vis[i] = 0;
    queue<int> q;
    q.push(i);
    while(q.size()) {
      int f = q.front();
      q.pop();
      if(vis[f]) continue;
      vis[f] = 1;
      for(pair<int,int> x: adj[f]) {
        if(vis[x.first]) continue;
        if(key[x.second]) {
          q.push(x.first);
        }
        else {
          can[x.second].push_back(x.first);
        }
      }
      if(!key[r[f]]) {
        key[r[f]] = 1;
        for(int x: can[r[f]]) {
          q.push(x);
        }
        can[r[f]].clear();
      }
    }
    int cnt = 0;
    for(int i=0; i<n; i++) cnt += vis[i];
    freq[i] = cnt;
    mn = min(mn, freq[i]);
  }
  for(int i=0; i<n; i++) {
    if(freq[i] == mn) {
      ans[i] = 1;
    }
    else {
      ans[i] = 0;
    }
  }
	return ans;
}
/*
problem=keys
grader_name=grad

g++ -std=c++17 -O2 -o "${problem}" "${grader_name}.cpp" "${problem}.cpp"
"./${problem}" < input.txt
*/

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