Submission #435883

#	Time	Username	Problem	Language	Result	Execution time	Memory
435883		Enkognit	Keys (IOI21_keys)	C++17	100 / 100	1769 ms	74144 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[300001];

    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;
bool QQ[300001];
vector<ll> lst1, lst2, lst3;
bool tt[300001], tl[300001], tu[300001];

void chk(int h)
{
    //cout << " chk " << h << " " << vv[h].size() << "\n";
    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();
    }
}

ll TT;

void add(int h)
{
    //q.push(h);
    //cout << " add\n";
    chk(col[h]);
    //cout << " end chk\n";
    lst1.pb(h);
    tt[h]=1;

    if (g.find_set(TT)!=g.find_set(h)) return;

    for (int i = 0; i < c[h].size(); i++)
        if (!tt[c[h][i].fi])
        {
            //cout << "? " << c[h][i].fi << "\n";
            if (tl[c[h][i].se])
            {
                q.push(c[h][i].fi);
                tt[c[h][i].fi]=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);
            }
        }
}

ll T=0;

void bfs(int h,vector<ll>& ee)
{

    TT=h;

    q.push(h);
    tt[h]=1;

    //cout << " bfs\n";

    while (!q.empty())
    {
        ll x=q.front();
        //cout << x << "\n";
        q.pop();
        ee.pb(x);
        //cout << x << "\n";
        if (g.find_set(x)!=g.find_set(h))
        {
            T=x;
        }
        //cout << x << "\n";
        add(x);
        //cout << "  " << x << " " << q.size() << "\n";
    }

    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()].clear();
        lst3.pop_back();
    }

}

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;

    ll lst=n*2;

    do{
        //cerr << "----\n";
        ll kol=0;
        merg.clear();
        for (int i = 0; i < n; i++)
            if (g.find_set(i)==i && !QQ[i])
        {
            kol++;
            //cout << " " << i << " :\n";
            T=-1;
            vector<ll> zz;
            bfs(i, zz);
            //cout << "-\n";
            if (T==-1)
            {
                //cout << "- " << i << "\n";
                QQ[i]=1;
                comp.pb(zz);
            }else
            {
                merg.pb(mp(i, T));
            }
            //cout << "--\n";
        }

        assert(kol*2<=lst);
        lst=kol;
        //cout << "!\n";
        for (int j = 0; j < merg.size(); j++)
        {
            g.unite_sets(merg[j].fi, merg[j].se);
            //cout << merg[j].fi << " -> " << merg[j].se << "\n";
        }
        //system("pause");
    }while (merg.size()>0);

    //cout << "----\n";

    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:77: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]
   77 |     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:194:27: 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]
  194 |         for (int j = 0; j < merg.size(); j++)
      |                         ~~^~~~~~~~~~~~~
keys.cpp:206: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]
  206 |     for (int i = 0; i < comp.size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp:212: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]
  212 |     for (int i = 0; i < comp.size(); i++)
      |                     ~~^~~~~~~~~~~~~
keys.cpp:213: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]
  213 |         if (mn==comp[i].size())
      |             ~~^~~~~~~~~~~~~~~~
keys.cpp:215:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |             for (int j = 0; j < comp[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~
keys.cpp:212:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  212 |     for (int i = 0; i < comp.size(); i++)
      |     ^~~
keys.cpp:219:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  219 |  return ans;
      |  ^~~~~~

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