Submission #441089

#	Time	Username	Problem	Language	Result	Execution time	Memory
441089		fcmalkcin	Keys (IOI21_keys)	C++17	67 / 100	3060 ms	55184 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=3e5+10;
const ll mod =998244353 ;
const ll base=3e18;

vector<pll> adj[maxn];
vector<ll> gr[maxn];
ll a[maxn];
ll cntnw=0;
bool dd[maxn];
ll chk[maxn];
bool h[maxn];
// key that we are having
ll par[maxn];
ll ans[maxn];
ll find_par(ll u)
{
    if (par[u]<0)
        return u;
    return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (dd[y])
    {
        dd[x]=1;
        return ;
    }
    assert(x!=y);
    par[y]+=par[x];
    par[x]=y;
}

bool dosth(ll x)
{
    cntnw++;
    vector<ll> vt;
    vt.pb(x);
    chk[x]=cntnw;
    h[a[x]]=1;
    vector<ll> vtc;
    for (int i=0; i<vt.size(); i++)
    {
        ll u=vt[i];
        if (u<base)
        {
            //if (ult[u]) cout <<"in vt "<<u<<" "<<x<<endl;
            for (auto p:adj[u])
            {
                ll to=p.ff;
                ll key=p.ss;
                //  if (x==270&&u==270&&to==177) cout <<key<<" "<<h[key]<<" "<<a[x]<<endl;
                if (chk[to]==cntnw)
                    continue;
                if (h[key])
                {
                    if (find_par(to)!=x)
                    {
                        for (auto to:vt)
                        {
                            if (to<base)
                                h[a[to]]=0;
                        }
                        for (auto to:vtc)
                        {
                            gr[to].clear();
                        }
                        dsu(x,find_par(to));
                        return true;
                    }
                    //  if (ult[to])cout <<"child of x"<<to<<" "<<u<<" "<<x<<endl;
                    chk[to]=cntnw;
                    vt.pb(to);
                    if (h[a[to]]==0)
                    {
                        h[a[to]]=1;
                        vt.pb(a[to]+base);
                    }
                }
                else
                {
                    vtc.pb(key);
                    gr[key].pb(to);
                }
            }
        }
        else
        {
            ll keynw=u-base;
            for (auto to:gr[keynw])
            {
                if (chk[to]==cntnw)
                    continue;
                if (find_par(to)!=x)
                {
                    for (auto to:vt)
                    {
                        if (to<base)
                            h[a[to]]=0;
                    }
                    for (auto to:vtc)
                    {
                        gr[to].clear();
                    }
                    dsu(x,find_par(to));
                    return true;
                }
                //  if (ult[to])cout <<"child of x"<<to<<" "<<u<<" "<<x<<endl;
                chk[to]=cntnw;
                vt.pb(to);
                if (h[a[to]]==0)
                {
                    h[a[to]]=1;
                    vt.pb(a[to]+base);
                }
            }
            gr[keynw].clear();
        }
    }
    dd[x]=1;
    ll cnt=0;
    for (auto to:vt)
    {
        if (to<base)
            h[a[to]]=0,cnt++;
    }
    for (auto to:vt)
    {
       if (to<base) ans[to]=cnt;
    }
    for (auto to:vtc)
    {
        gr[to].clear();
    }
    return false;
}
vector<int> find_reachable(vector<int> r, vector<int>  u, vector<int> v, vector<int> c)
{
    memset(par,-1,sizeof(par));
    memset(ans,0x3f,sizeof(ans));
    ll n=r.size();
    ll m=u.size();
    cntnw=0;

    vector<int> res;
    for (int i=1; i<=m; i++)
    {
        adj[u[i-1]+1].pb(make_pair(v[i-1]+1,c[i-1]));
        adj[v[i-1]+1].pb(make_pair(u[i-1]+1,c[i-1]));
    }
    for (int i=1; i<=n; i++)
        a[i]=r[i-1];

    while (1)
    {
        bool chk=false;
        for (int i=1; i<=n; i++)
        {
            if (!dd[i]&&par[i]<0)
            {
                chk|=dosth(i);
            }
        }
        if (!chk)
            break;
    }
    ll mn=base;
    for (int i=1; i<=n; i++)
        mn=min(mn,ans[i]);

    for (int i=1; i<=n; i++)
    {
        adj[i].clear();
        dd[i]=0;
        chk[i]=0;
        if (ans[i]==mn)
            res.pb(1);
        else
            res.pb(0);
    }
    return res;
}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        //  freopen("test.out", "w", stdout);
    }
    ll n, m;
    cin>> n>> m;
    vector<int> r;
    for (int i=1; i<=n; i++)
    {
        int x;
        cin>> x;
        r.pb(x);
    }
    vector<int> u,v,c;
    for (int i=1; i<=m; i++)
    {
        int x, y, w;
        cin>> x>> y>> w;
        u.pb(x);
        v.pb(y);
        c.pb(w);
    }

    vector<int> ans=find_reachable(r,u,v,c);
    for (auto to:ans) cout <<to<<" ";

}*/
/*
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2*/
/*
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
*/
/*
3
1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1
*/
/*
3
1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1
*/

Compilation message (stderr)

keys.cpp: In function 'bool dosth(long long int)':
keys.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i=0; i<vt.size(); i++)
      |                   ~^~~~~~~~~~

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