Submission #441366

#	Time	Username	Problem	Language	Result	Execution time	Memory
441366		daniel920712	Keys (IOI21_keys)	C++17	37 / 100	3053 ms	33792 KiB

keys

#include <vector>
#include <queue>
#include <utility>


using namespace std;
bool have[300005];
bool vis[300005];
int con[300005];

vector < int > ans;
vector < pair < int , int > > Next[300005];
vector < int > all[300005];
queue < int > BFS;
vector < int > find_reachable(vector < int > r, vector < int > u, vector < int > v, vector < int > c)
{
	int N=r.size(),M=u.size(),i,j,now,small=2e9;
	for(i=0;i<M;i++)
    {
        Next[u[i]].push_back(make_pair(v[i],c[i]));
        Next[v[i]].push_back(make_pair(u[i],c[i]));
    }
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            all[j].clear();
            vis[j]=0;
            have[j]=0;
        }
        BFS.push(i);
        while(!BFS.empty())
        {
            now=BFS.front();
            BFS.pop();
            if(vis[now]) continue;
            vis[now]=1;
            con[i]++;
            if(!have[r[now]])
            {
                have[r[now]]=1;
                for(auto j:all[r[now]]) BFS.push(j);
                all[r[now]].clear();
            }
            for(auto j:Next[now])
            {
                if(have[j.second]) BFS.push(j.first);
                else all[j.second].push_back(j.first);
            }
        }

    }
    for(i=0;i<N;i++) small=min(small,con[i]);
    for(i=0;i<N;i++) ans.push_back(con[i]==small);

	return ans;
}

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