Submission #1290315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290315		MMihalev	Keys (IOI21_keys)	C++20	9 / 100	677 ms	79744 KiB

keys

#include<iostream>
#include<algorithm>
#include <vector>
#include<set>
#include "keys.h"
using namespace std;
const int MAX_N=3e5+5;
int parent[MAX_N];
int sz[MAX_N];
set<int>keys[MAX_N];
vector<int>nodes[MAX_N];
vector<pair<int,pair<int,int>>>edges;
set<int>parents;
int Find(int u)
{
    if(parent[u]==u)return u;
    return parent[u]=Find(parent[u]);
}
void Merge(int u,int v)
{
    int urt=Find(u);
    int vrt=Find(v);
    if(urt==vrt)return;

    if(sz[urt]>sz[vrt])swap(urt,vrt);

    parent[urt]=vrt;
    parents.erase(urt);
    sz[vrt]+=sz[urt];
    for(int key:keys[urt])keys[vrt].insert(key);
    for(int node:nodes[urt])nodes[vrt].push_back(node);
    set<int>().swap(keys[urt]);
    vector<int>().swap(nodes[urt]);
}
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(),m=u.size();

    vector<int>ans;
    ans.resize(n);

    for(int i=0;i<n;i++)
    {
        parent[i]=i;
        sz[i]=1;
        nodes[i].push_back(i);
        keys[i].insert(r[i]);
        parents.insert(i);
    }

    for(int i=0;i<m;i++)
    {
        edges.push_back({c[i],{u[i],v[i]}});
    }

    for(int times=0;times<20;times++)
    {
        vector<int>cnt;
        cnt.resize(n);
        bool stop=0;

        for(auto [c,edge]:edges)
        {
            int u=edge.first,v=edge.second;

            int urt=Find(u);
            int vrt=Find(v);
            if(urt==vrt)continue;

            if(keys[urt].count(c))cnt[urt]=1;
            if(keys[vrt].count(c))cnt[vrt]=1;
        }

        int curmin=1e9;
        vector<int>curminnodes;
        for(int u:parents)
        {
            if(!cnt[u])
            {
                stop=1;
                if(sz[u]<curmin)
                {
                    curmin=sz[u];
                    curminnodes=nodes[u];
                }
                else if(sz[u]==curmin)
                {
                    for(int v:nodes[u])curminnodes.push_back(v);
                }
            }
        }

        if(stop)
        {
            for(int u:curminnodes)ans[u]=1;
            return ans;
        }

        for(auto [c,edge]:edges)
        {
            int u=edge.first,v=edge.second;

            int urt=Find(u);
            int vrt=Find(v);
            if(urt==vrt)continue;

            Merge(urt,vrt);
        }
    }
}

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:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^

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