Submission #435755

#	Time	Username	Problem	Language	Result	Execution time	Memory
435755		Enkognit	Keys (IOI21_keys)	C++17	0 / 100	2141 ms	1048580 KiB

keys

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define y1 Enkognit

using namespace std;

ll n, m, k, col[300001];
vector<pll> c[300001];

struct dsu
{
    ll d[1000001];

    void make_sets(int h)
    {
        for (int i = 0; i < h; i++)
            d[i]=i;
    }

    ll find_set(int h)
    {
        if (h==d[h]) return h; else return d[h]=find_set(d[h]);
    }

    bool unite_sets(int x,int y)
    {
        x=find_set(x);
        y=find_set(y);
        d[x]=y;
        return x!=y;
    }
} g;

vector<ll> vv[300001];

queue<ll> q;
vector<ll> lst1, lst2, lst3;
bool tt[300001], tl[300001], tu[300001];

void chk(int h)
{
    tl[h]=1;
    lst2.pb(h);
    while (vv[h].size())
    {
        if (!tt[vv[h].back()])
        {
            tt[vv[h].back()]=1;
            q.push(vv[h].back());
        }
        vv[h].pop_back();
    }
}

void add(int h)
{
    q.push(h);
    chk(col[h]);
    lst1.pb(h);
    tt[h]=1;
    for (int i = 0; i < c[h].size(); i++)
        if (!tt[c[h][i].fi])
        {
            if (tl[c[h][i].se])
            {
                q.push(h);
                tt[h]=1;
            }else
            {
                if (!tu[c[h][i].se])
                {
                    tu[c[h][i].se]=1;
                    lst3.pb(c[h][i].se);
                }
                vv[c[h][i].se].pb(c[h][i].fi);
            }
        }
}

vector<ll> bfs(int h)
{
    q.push(h);

    vector<ll> ee;

    while (!q.empty())
    {
        ll x=q.front();
        q.pop();
        ee.pb(x);
        add(x);
    }

    while (lst1.size())
    {
        tt[lst1.back()]=0;
        lst1.pop_back();
    }
    while (lst2.size())
    {
        tl[lst2.back()]=0;
        lst2.pop_back();
    }
    while (lst3.size())
    {
        tu[lst3.back()]=0;
        vv[lst3.back()].pop_back();
        lst3.pop_back();
    }

    return ee;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> cc) {

    n=r.size();

    for (int i = 0; i < n; i++)
        col[i]=r[i];

    m=u.size();

    g.make_sets(n);

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

    vector<pll> merg;
    vector<vector<ll> > comp;

    do{
        merg.clear();
        for (int i = 0; i < n; i++)
            if (g.find_set(i)==i)
        {
            vector<ll> zz=bfs(i);
            if (g.find_set(zz.back())==g.find_set(i))
            {
                comp.pb(zz);
            }else
            {
                g.unite_sets(i, zz.back());
            }
        }
    }while (merg.size()>0);

    ll mn=1e18;

    for (int i = 0; i < comp.size(); i++)
        mn=min(mn, (ll)comp[i].size());

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

    for (int i = 0; i < comp.size(); i++)
        if (mn==comp[i].size())
        {
            for (int j = 0; j < comp[i].size(); j++)
                ans[comp[i][j]]=1;
        }

	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void add(int)':
keys.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < c[h].size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:159:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (int i = 0; i < comp.size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp:165:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for (int i = 0; i < comp.size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp:166:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         if (mn==comp[i].size())
      |             ~~^~~~~~~~~~~~~~~~
keys.cpp:168:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             for (int j = 0; j < comp[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~
keys.cpp:165:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  165 |     for (int i = 0; i < comp.size(); i++)
      |     ^~~
keys.cpp:172:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  172 |  return ans;
      |  ^~~~~~

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