Submission #623110

#	Time	Username	Problem	Language	Result	Execution time	Memory
623110		Hanksburger	Keys (IOI21_keys)	C++17	37 / 100	3067 ms	36804 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[300005];
bool visited[300005], key[300005];
vector<int> vec[300005], ans;
int p[300005];
queue<int> q;
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    int n=r.size(), mn=1e9;
    for (int i=0; i<c.size(); i++)
    {
        adj[u[i]].push_back({v[i], c[i]});
        adj[v[i]].push_back({u[i], c[i]});
    }
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            visited[j]=key[j]=0;
            vec[j].clear();
        }
        q.push(i);
        visited[i]=1;
        while (!q.empty())
        {
            int u=q.front();
            q.pop();
            key[r[u]]=1;
            for (int j=0; j<vec[r[u]].size(); j++)
            {
                if (!visited[vec[r[u]][j]])
                {
                    q.push(vec[r[u]][j]);
                    visited[vec[r[u]][j]]=1;
                }
            }
            for (int j=0; j<adj[u].size(); j++)
            {
                if (key[adj[u][j].second])
                {
                    if (!visited[adj[u][j].first])
                    {
                        q.push(adj[u][j].first);
                        visited[adj[u][j].first]=1;
                    }
                }
                else
                    vec[adj[u][j].second].push_back(adj[u][j].first);
            }
        }
        for (int j=0; j<n; j++)
            p[i]+=visited[j];
    }
    for (int i=0; i<n; i++)
        mn=min(mn, p[i]);
    for (int i=0; i<n; i++)
        ans.push_back(p[i]==mn);
    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:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i=0; i<c.size(); i++)
      |                   ~^~~~~~~~~
keys.cpp:31:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for (int j=0; j<vec[r[u]].size(); j++)
      |                           ~^~~~~~~~~~~~~~~~~
keys.cpp:39:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for (int j=0; j<adj[u].size(); j++)
      |                           ~^~~~~~~~~~~~~~

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