Submission #835746

#	Time	Username	Problem	Language	Result	Execution time	Memory
835746		JakobZorz	Keys (IOI21_keys)	C++17	37 / 100	3055 ms	29184 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];
vector<pair<int,int>>nodes[300000];
int min_res=1e6;
int n,m;

int 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()){
        int node=q.front();
        q.pop();
        
        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);
                }
            }
        }
    }
    
    return (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];
    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]});
    }
    
    for(int i=0;i<n;i++){
        res[i]=search(i);
        min_res=min(min_res,search(i));
    }
    
    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 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:70:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |     for(int i=0;i<n;i++)
      |     ^~~
keys.cpp:72:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |  return ans;
      |  ^~~~~~

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