Submission #443406

#	Time	Username	Problem	Language	Result	Execution time	Memory
443406		urd05	Keys (IOI21_keys)	C++17	37 / 100	946 ms	24248 KiB

keys

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

int ret[2000];
int p[2000];
set<int> s[2000];
bool used[2000];
typedef pair<int,int> P;
vector<P> edge[2000];

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    if (s[a].size()<s[b].size()) {
        swap(a,b);
    }
    for(auto now:s[b]) {
        if (!used[now])
            s[a].insert(now);
    }
    p[a]+=p[b];
    p[b]=a;
    s[b].clear();
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n=r.size();
	int m=c.size();
	for(int i=0;i<m;i++) {
	    edge[c[i]].push_back(P(u[i],v[i]));
	}
	int mn=1e9;
	vector<int> vec(n);
	for(int i=0;i<n;i++) {
	    memset(p,-1,sizeof(p));
	    for(int j=0;j<n;j++) {
	        used[j]=false;
	        s[j].clear();
	        s[j].insert(r[j]);
	    }
	    while (1) {
	        int key=-1;
	        vector<int> temp;
	        for(auto now:s[find(i)]) {
	            if (used[now]) {
                    temp.push_back(now);
	                continue;
	            }
	            else {
	                key=now;
	                break;
	            }
	        }
	        for(int j=0;j<temp.size();j++) {
                s[find(i)].erase(temp[j]);
	        }
	        //printf("%d\n",key);
	        if (key==-1) {
	            break;
	        }
	        used[key]=true;
	        for(int j=0;j<edge[key].size();j++) {
	            merge(edge[key][j].first,edge[key][j].second);
	        }
	    }
	    ret[i]=-p[find(i)];
	    mn=min(mn,ret[i]);
	}
	for(int i=0;i<n;i++) {
	    if (ret[i]==mn) {
	        vec[i]=1;
	    }
	    else {
	        vec[i]=0;
	    }
	}
	return vec;
}

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:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |          for(int j=0;j<temp.size();j++) {
      |                      ~^~~~~~~~~~~~
keys.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |          for(int j=0;j<edge[key].size();j++) {
      |                      ~^~~~~~~~~~~~~~~~~

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