Submission #835752

#	Time	Username	Problem	Language	Result	Execution time	Memory
835752		JakobZorz	Keys (IOI21_keys)	C++17	100 / 100	2241 ms	67960 KiB

keys

#include"keys.h"
#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;


int res[300000];
int key[300000];
bool done[300000];
vector<pair<int,int>>nodes[300000];
int min_res=1e6;
int n,m;

void search(int x){
    unordered_set<int>keys,visited;
    unordered_map<int,vector<int>>blocked;
    queue<int>q;
    visited.insert(x);
    q.push(x);
    
    while(!q.empty()){
        if(visited.size()>min_res)
            return;
        
        int node=q.front();
        q.pop();
        if(done[node])
            return;
        
        if(keys.find(key[node])==keys.end()){
            keys.insert(key[node]);
            for(int node2:blocked[key[node]]){
                if(visited.find(node2)==visited.end()){
                    visited.insert(node2);
                    q.push(node2);
                }
            }
        }
        
        for(auto ne:nodes[node]){
            if(keys.find(ne.second)==keys.end()){
                blocked[ne.second].push_back(ne.first);
            }else{
                if(visited.find(ne.first)==visited.end()){
                    visited.insert(ne.first);
                    q.push(ne.first);
                }
            }
        }
    }
    
    for(int i:visited)
        res[i]=min(res[i],(int)visited.size());
}

vector<int>find_reachable(vector<int>r,vector<int>u,vector<int>v,vector<int>c){
    n=(int)r.size();
    m=(int)c.size();
    
    for(int i=0;i<n;i++){
        key[i]=r[i];
        res[i]=1e6;
    }
    vector<int>nd;
    for(int i=0;i<m;i++){
        nodes[u[i]].push_back({v[i],c[i]});
        nodes[v[i]].push_back({u[i],c[i]});
        nd.push_back(u[i]);
        nd.push_back(v[i]);
    }
    
    for(int i=0;i<2*m;i++){
        swap(nd[i],nd[rand()%(2*m)]);
    }
    
    for(int i:nd){
        if(!done[i]){
            search(i);
            min_res=min(min_res,res[i]);
            done[i]=true;
        }
    }
    
    for(int i=0;i<n;i++){
        if(!done[i]){
            search(i);
            min_res=min(min_res,res[i]);
            done[i]=true;
        }
    }
    
    vector<int>ans(n);
    for(int i=0;i<n;i++)
        ans[i]=res[i]==min_res;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void search(int)':
keys.cpp:26:26: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         if(visited.size()>min_res)
      |            ~~~~~~~~~~~~~~^~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:97:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |     for(int i=0;i<n;i++)
      |     ^~~
keys.cpp:99:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   99 |  return ans;
      |  ^~~~~~

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