Submission #1326741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326741		BigBadBully	Keys (IOI21_keys)	C++20	0 / 100	1 ms	332 KiB

keys

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

struct dsu{
    int n;
    vector<int> par,sz;
    dsu(int s)
    {
        n = s;
        par.resize(n);
        sz.resize(n,1);
        for(int i =0 ; i< n; i++)   
            par[i] = i;
    }
    int fnd(int x)
    {
        if(par[x]==x)return x;
        return par[x] = fnd(par[x]);
    }
    bool unite(int a,int 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) {
	int n =r.size();
    int m = u.size();
    dsu mile(n);
    vector<vector<pii>> cols(n);
    for(int i = 0; i < m; i++)
        cols[c[i]].push_back({u[i],v[i]});
    vector<pii> edges;
    vector<int> coord;
    for(int i = 0; i< n; i++)
        coord.push_back(i);
    for(int col = 0;col < n; col++)
    {
        for(pii x : cols[col])
            mile.unite(x.ff,x.ss);
        for(pii x :cols[col])
        {
            int a = x.ff;
            for(int it = 0;it < 2;it++)
            {   
                edges.push_back({(col+1)*n+mile.fnd(a),a});
                if(r[a]==col)
                    edges.push_back({a,(col+1)*n+mile.fnd(a)});
                coord.push_back(a);
                coord.push_back((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...
    int k =coord.size();
    vector<vector<int>> graph(k);
    for(pii x:edges)
        graph[x.ff].push_back(x.ss);
    vector<vector<int>> rev(k);
    for(pii x:edges)
        rev[x.ss].push_back(x.ff);
    vector<int> ord;
    vector<int> vis(k,0);
    vector<int> scc(k);
    function<void(int,int)> dfs = [&](int cur,int r){
        if(vis[cur])return;
        if(r!=-1)
            scc[cur] = r;
        vis[cur] = 1;
        for(int a:graph[cur])
            dfs(a,r);
        if(r==-1)
        ord.push_back(cur);
    };
    reverse(ord.begin(),ord.end());
    
    for(int i = 0; i< k; i++)
        dfs(i,-1);
    vis.assign(k,0);
    function<void(int,int)> rfs = [&](int cur,int r)
    {
        if(vis[cur])return;
        scc[cur] = r;
        vis[cur] = 1;
        for(int a: rev[cur])
            rfs(a,r);
    };
    for(int x:ord)
        dfs(x,x);
    vector<int> sz(k,0);
    vector<int> 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(int i = 0; i< n; i++)
        sz[scc[i]]++;
    int mini = n+1;
    for(int i =0 ; i < n; i++)
        if(moze[scc[i]])
            mini = min(mini,sz[scc[i]]);
    for(int 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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33