Submission #1223131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223131		CELD_07	Keys (IOI21_keys)	C++20	37 / 100	3093 ms	33308 KiB

keys

#include "keys.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<pair<ll, ll>>> adj;
vector<ll> v;
inline ll bfs(ll n, ll a){
vector<bool> visited(a+1, 0), visited1(a+1, 0);
vector<vector<ll>> v1(a+1);
queue<ll> q;
q.push(n);
ll res=0;
while(!q.empty()){
ll o=q.front();
q.pop();
if(visited[o])continue;
res++;
for(auto& [x, y]: adj[o]){
if(!visited1[y])v1[y].push_back(x);
else q.push(x);
}
visited1[v[o]]=1;
visited[o]=1;
while(!v1[v[o]].empty()){
if(!visited[v1[v[o]].back()]){
q.push(v1[v[o]].back());
}
v1[v[o]].pop_back();
}
}
vector<bool>().swap(visited);
vector<bool>().swap(visited1);
vector<vector<ll>>().swap(v1);
return res;

}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v2, vector<int> c) {
ll n=r.size();
vector<vector<pair<ll, ll>>>().swap(adj);
vector<ll>().swap(v);
v.resize(n+1);
adj.resize(n+1);
for(int i=0; i<u.size(); i++){
adj[u[i]].push_back({v2[i], c[i]});
adj[v2[i]].push_back({u[i], c[i]});
}
vector<int>res(n, 1);
for(int i=0; i<n; i++)v[i]=r[i];
for(int i=0; i<n; i++)res[i]=bfs(i, n);
ll k=*min_element(all(res));
for(int i=0; i<n; i++)res[i]=(res[i]==k ? 1 : 0);
return res;
}

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