Submission #1236393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236393		AlperenT_	Keys (IOI21_keys)	C++20	39 / 100	451 ms	62640 KiB

keys

#include <bits/stdc++.h> 
#include "keys.h"
#pragma GCC optimize("O3,unroll-loops") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 3e5  + 10 , inf = 1e9+ 10 , mod = 998244353;

int par[maxn] , mark[maxn] , C[maxn] , t[maxn] , ans[maxn];
int mp[maxn] ;
int find(int v){
    if(par[v] == v)return v; 
    return par[v] = find(par[v]);
}

void mrg(int v, int u){
    v = find(v) ; u = find(u);
    if(v==u){
        return; 
    }
    mp[u] |= mp[v] ;
    par[v] = u ;
    return; 
}
vector <int> tp , Gr[maxn] , G[maxn];
void dfs(int v){
    mark[v] = 1;
    for(int u : G[v]){
        if(mark[u] == 1)continue ;
        dfs(u);
    }
    tp.pb(v); 
}
int cnt =0; 
void dfs2(int v){
    mark[v] =1;
    C[v] = cnt;
    for(int u : Gr[v]){
        if(mark[u] == 1)continue;
        dfs2(u) ; 
    }
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c){
    int n = sz(r)-1 ;
    int m = sz(u)-1 ;
    rep(i ,0 , n)par[i] = i ;
    
    rep(i ,0 ,n)mp[i] = (1<<r[i]) ;
    int ted =0 ;
    while(1){
        ted++;
        rep(i ,0 , n){
            G[i].clear() ;
            Gr[i].clear() ;
            mark[i] =0 ;
        }
        rep(i , 0 ,m){
            if(find(v[i]) == find(u[i]))continue ;
            if(mp[find(u[i])]>>c[i]&1){
                G[find(u[i])].pb(find(v[i])) ;
            }
            if(mp[find(v[i])]>>c[i]&1){
                G[find(v[i])].pb(find(u[i])) ;
            }
        }
        rep(i , 0 ,n){
            for(int u  : G[i]){
                Gr[u].pb(i) ;
            }
        }
        tp.clear();
        rep(i ,0 , n){
            if(mark[i] == 1)continue; 
            dfs(i);
        }
        reverse(all(tp));
        rep(i , 0 ,n)mark[i] = 0;
        cnt =0 ;
        for(int v : tp){
            if(mark[v] == 1){
                continue ;
            }
            dfs2(v); 
            cnt++ ;
        }
        bool ok = 0 ;
        rep(v , 0  ,n){
            for(int u : G[v]){
                if(C[v] == C[u]){
                    mrg(v,u) ;
                    ok =1 ;
                }
            }
        }
        if(ok == 0 || ted==40){
            rep(i ,0 , n)t[find(i)]++;
            int mn = n+1;
            rep(i , 0 ,n){
                if(find(i) != i)continue ;
                if(sz(G[i]) == 0){
                    mn = min(mn , t[i]);
                }
            }
            rep(i , 0 ,n){
                if(t[find(i)] == mn && sz(G[find(i)])==0){
                    ans[i] =1 ;
                }
            }
            break ;    
        }
    }
    vector <int> vec;
    rep(i , 0 ,n){
        vec.pb(ans[i]);
    }
    return vec; 
}

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