Submission #593438

#	Time	Username	Problem	Language	Result	Execution time	Memory
593438		nohaxjustsoflo	Keys (IOI21_keys)	C++17	100 / 100	1138 ms	95980 KiB

keys

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=3e5+5;
const int mod=998244353;
const int mxlogN=20;
const int mxK=26;
const int inf=30000;
const int K=600;

struct DSU
{
    vector<int> size,p;
    int comp;
    void build(int n)
    {
        size=vector<int>(n,1);
        p=vector<int>(n);
        iota(p.begin(),p.end(),0);
        comp=n;
    }
    int get(int x)
    {
        if(p[x]^x) p[x]=get(p[x]);
        return p[x];
    }
    bool unite(int a, int b)
    {
        a=get(a),b=get(b);
        if(a==b) return 0;
        if(size[a]>size[b]) swap(a,b);
        p[a]=b;
        size[b]+=size[a];
        comp--;
        return 1;
    }
};
int who[mxN], nex[mxN];
int WHO(int i)
{
    if(who[i]^i) who[i]=WHO(who[i]);
    return who[i];
}
vector<int> conn[mxN];
set<int> keys[mxN];
set<pair<int,int>> doors[mxN];
void add_door(int i, int c, int x)
{
    if(keys[i].count(c)) conn[i].push_back(x);
    else doors[i].insert({c,x});
}
void add_key(int i, int c)
{
    if(!keys[i].count(c))
    {
        keys[i].insert(c);
        auto it=doors[i].lower_bound({c,-1});
        while(it!=doors[i].end()&&it->first==c)
        {
            auto jt=next(it);
            conn[i].push_back(it->second);
            doors[i].erase(it);
            it=jt;
        }
    }
}
void merge(int u, int v)
{
    ///prebaci ove u v
    ///ako ovo neradi probaj sum, pa sve da prebacis
    int usz=conn[u].size()+keys[u].size()+doors[u].size();
    int vsz=conn[v].size()+keys[v].size()+doors[v].size();
    if(usz>vsz)
    {
        conn[u].swap(conn[v]);
        keys[u].swap(keys[v]);
        doors[u].swap(doors[v]);
    }

    for(auto x:conn[u]) conn[v].push_back(x);
    conn[u].clear();

    for(auto c:keys[u]) add_key(v,c);
    keys[u].clear();

    for(auto par:doors[u]) add_door(v,par.first,par.second);
    doors[u].clear();

}
int cnt[mxN];
bool can[mxN];
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    int n=r.size(),m=u.size();
    for(int i=0; i<m; i++)
    {
        add_door(u[i],c[i],v[i]);
        add_door(v[i],c[i],u[i]);
    }
    for(int i=0; i<n; i++)
    {
        add_key(i,r[i]);
        who[i]=nex[i]=i;
    }
    DSU dsu; dsu.build(n);
    for(int i=0; i<n; i++)
    {
        while(conn[i].size())
        {
            int j=WHO(conn[i].back());
            conn[i].pop_back();
            if(dsu.get(i)==dsu.get(j))
            {
                vector<int> vis;
                while(j!=i)
                {
                    int k=WHO(nex[j]);
                    who[j]=i;
                    vis.push_back(j);
                    j=k;
                }
                for(int j:vis) merge(j,i);
            }
            else
            {
                nex[i]=j;
                dsu.unite(i,j);
                break;
            }
        }
        if(nex[i]==i) can[i]=1;
    }
    for(int i=0; i<n; i++) cnt[WHO(i)]++;
    int mn=n+1;
    for(int i=0; i<n; i++) if(can[i]) mn=min(mn,cnt[i]);
    vector<int> ans(n,0);
    for(int i=0; i<n; i++) if(cnt[WHO(i)]==mn&&can[WHO(i)]) ans[i]=1;
    return ans;
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m; cin >> n >> m;
    vector<int> r(n),u(m),v(m),c(m);
    for(int i=0; i<n; i++) cin >> r[i];
    for(int i=0; i<m; i++) cin >> u[i];
    for(int i=0; i<m; i++) cin >> v[i];
    for(int i=0; i<m; i++) cin >> c[i];
    auto ans=find_reachable(r,u,v,c);
    for(auto i:ans) cout << i << " ";
    cout << "\n";
}
*/
/*
7 10
0 1 1 2 2 1 2
0 0 1 1 2 3 3 4 4 5
1 2 2 3 3 4 5 5 6 6
0 0 1 0 0 1 2 0 2 1
*/

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