Submission #824564

#	Time	Username	Problem	Language	Result	Execution time	Memory
824564		andrei_boaca	Keys (IOI21_keys)	C++17	37 / 100	3073 ms	39652 KiB

keys

#include <vector>
#include <bits/stdc++.h>
#include "keys.h"
//#include "grader.cpp"
using namespace std;
typedef pair<int,int> pii;
vector<pii> muchii[300005];
bool use[300005];
int room[300005];
int cnt[300005];
bool found[300005];
vector<pii> g[300005];
int n,m;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    n=r.size();
    m=u.size();
    for(int i=0;i<m;i++)
    {
        int a=u[i],b=v[i],cul=c[i];
        muchii[a].push_back({b,cul});
        muchii[b].push_back({a,cul});
        g[cul].push_back({a,b});
    }
    vector<int> ans;
    for(int i=0;i<n;i++)
    {
        ans.push_back(0);
        room[i]=r[i];
    }
    int minim=1e9;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            use[j]=0;
            found[j]=0;
        }
        queue<int> coada;
        coada.push(i);
        while(!coada.empty())
        {
            int nod=coada.front();
            coada.pop();
            if(use[nod])
                continue;
            use[nod]=1;
            int cul=room[nod];
            if(!found[cul])
            {
                found[cul]=1;
                for(pii p:g[cul])
                {
                    int a=p.first;
                    int b=p.second;
                    if(!use[a])
                        swap(a,b);
                    if(use[a]&&!use[b])
                        coada.push(b);
                }
            }
            for(pii p:muchii[nod])
            {
                int a=p.first;
                int cc=p.second;
                if(found[cc])
                    if(!use[a])
                        coada.push(a);
            }
        }
        cnt[i]=0;
        for(int j=0;j<n;j++)
            cnt[i]+=use[j];
        minim=min(minim,cnt[i]);
    }
    for(int i=0;i<n;i++)
        if(cnt[i]==minim)
            ans[i]=1;
    return ans;
}

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