Submission #1326747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326747		BigBadBully	Keys (IOI21_keys)	C++20	20 / 100	473 ms	108864 KiB

keys

#include <bits/stdc++.h>

#define ll long long
#define pii pair<ll,ll>
#define ff first
#define ss second
using namespace std;


struct dsu{
    ll n;
    vector<ll> par,sz;
    dsu(ll s)
    {
        n = s;
        par.resize(n);
        sz.resize(n,1);
        for(ll i =0 ; i< n; i++)   
            par[i] = i;
    }
    ll fnd(ll x)
    {
        if(par[x]==x)return x;
        return par[x] = fnd(par[x]);
    }
    bool unite(ll a,ll b)
    {
        a =fnd(a),b = fnd(b);
        if(a==b)return true;
        if(sz[a]>sz[b])
            swap(a,b);
        par[a] = b;
        sz[b]+=sz[a];
        return false;
    }
};

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	ll n =r.size();
    ll m = u.size();
    dsu mile(n);
    vector<vector<pii>> cols(n);
    for(ll i = 0; i < m; i++)
        cols[c[i]].push_back({u[i],v[i]});
    vector<pii> edges;
    vector<ll> coord;
    for(ll i = 0; i< n; i++)
        coord.push_back(i);
    for(ll col = 0;col < n; col++)
    {
        for(pii x : cols[col])
            mile.unite(x.ff,x.ss);
        for(pii x :cols[col])
        {
            ll a = x.ff;
            for(ll it = 0;it < 2;it++)
            {   
                edges.push_back({(2*col+1)*n+mile.fnd(a),a});
                if(r[a]==col)
                    edges.push_back({a,(2*col+1)*n+mile.fnd(a)});
                coord.push_back(a);
                coord.push_back((2*col+1)*n+mile.fnd(a));
                a = x.ss;
            }
        }
        for(pii x:cols[col])
            mile.par[x.ff]=x.ff,mile.par[x.ss]=x.ss,
            mile.sz[x.ff]=1,mile.sz[x.ss]=1;
    }
    sort(coord.begin(),coord.end());
    coord.resize(unique(coord.begin(),coord.end())-coord.begin());
    for(pii&x:edges)
        x.ff = lower_bound(coord.begin(),coord.end(),x.ff)-coord.begin(),
        x.ss=lower_bound(coord.begin(),coord.end(),x.ss)-coord.begin();
    //samo k koristit...
    ll k =coord.size();
    vector<vector<ll>> graph(k);
    for(pii x:edges)
        graph[x.ff].push_back(x.ss);
    vector<vector<ll>> rev(k);
    for(pii x:edges)
        rev[x.ss].push_back(x.ff);
    vector<ll> ord;
    vector<ll> vis(k,0);
    function<void(ll)> dfs = [&](ll cur){
        if(vis[cur])return;
        vis[cur] = 1;
        for(ll a:graph[cur])
            dfs(a);
        ord.push_back(cur);
    };
    vector<ll> scc(k);
    for(ll i = 0; i< k; i++)
        dfs(i);
    reverse(ord.begin(),ord.end());
    vis.assign(k,0);
    function<void(ll,ll)> rfs = [&](ll cur,ll r)
    {
        if(vis[cur])return;
        scc[cur] = r;
        vis[cur] = 1;
        for(ll a: rev[cur])
            rfs(a,r);
    };
    for(ll x:ord)
        rfs(x,x);
    vector<ll> sz(k,0);
    vector<ll> moze(k,1);
    for(pii x:edges)
        if(scc[x.ff]!=scc[x.ss])
            moze[scc[x.ff]] = 0;
    
    vector<int> ans(n,0);
    for(ll i = 0; i< n; i++)
        sz[scc[i]]++;
    ll mini = n+1;
    for(ll i =0 ; i < n; i++)
        if(moze[scc[i]])
            mini = min(mini,sz[scc[i]]);
    for(ll i = 0; i < n; i++)
        if(moze[scc[i]] && sz[scc[i]]==mini)
            ans[i] = 1;
    if(mini==n+1)
        ans.assign(n,1);
	return ans;
}

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