Submission #1024228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024228		Abito	Keys (IOI21_keys)	C++17	37 / 100	3054 ms	36552 KiB

keys

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=3e5+5;
int n,r[N],p[N];
vector<pair<int,int>> adj[N],c[N];
bool vis[N],key[N];
void getp(int s){
    for (int i=0;i<n;i++) vis[i]=0,key[i]=0;
    vis[s]=1;
    queue<int> q;q.push(s);
    while (!q.empty()){
        p[s]++;
        int x=q.front();
        q.pop();
        if (!key[r[x]]){
            key[r[x]]=1;
            for (auto u:c[r[x]]){
                if (vis[u.F]==vis[u.S]) continue;
                if (vis[u.F]){
                    vis[u.S]=1;
                    q.push(u.S);
                }
                else{
                    vis[u.F]=1;
                    q.push(u.F);
                }
            }
        }
        for (auto u:adj[x]){
            if (vis[u.F] || !key[u.S]) continue;
            vis[u.F]=1;
            q.push(u.F);
        }
    }return;
}
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	n=R.size();
	vector<int> ans(n);
	for (int i=0;i<U.size();i++){
        adj[U[i]].pb({V[i],C[i]});
        adj[V[i]].pb({U[i],C[i]});
        c[C[i]].pb({U[i],V[i]});
	}
	for (int i=0;i<n;i++) r[i]=R[i];
	int mn=INT_MAX;
    for (int i=0;i<n;i++){
        getp(i);
        mn=min(p[i],mn);
    }
    for (int i=0;i<n;i++) ans[i]=(p[i]==mn);
	return ans;
}

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:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  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