Submission #495622

#	Time	Username	Problem	Language	Result	Execution time	Memory
495622		PedroBigMan	Keys (IOI21_keys)	C++17	37 / 100	3027 ms	33416 KiB

keys

/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
#define VV(vvvv,NNNN,xxxx); REP(i,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

ll N,M; vector<bool> key; vector<vector<ll> > nxt; vector<vector<pl> > adj; vector<ll> r; vector<bool> visited; vector<ll> newkeys;
ll nei; vector<ll> newnewkeys;

void Reset()
{
	REP(i,0,N) {key[i]=false; nxt[i].clear(); visited[i]=false;}
	newkeys.clear();
}

void DFS(ll s)
{
	if(visited[s]) {return;}
	visited[s]=true; if(!key[r[s]]) {key[r[s]]=true; newnewkeys.pb(r[s]);}
	REP(i,0,adj[s].size())
	{
		nei=adj[s][i].ff;
		if(visited[nei]) {continue;}
		if(key[adj[s][i].ss]) {DFS(nei);}
		else {nxt[adj[s][i].ss].pb(nei);}
	}	
}

vector<ll> find_reachable(vector<ll> rr, vector<ll> u, vector<ll> v, vector<ll> c) 
{
	r=rr; N = r.size(); M = u.size(); VV(key,N,false); VV(adj,N,{});
	REP(i,0,M) {adj[u[i]].pb({v[i],c[i]}); adj[v[i]].pb({u[i],c[i]});}
	vector<ll> p; VV(p,N,0); VV(nxt,N,{}); VV(visited,N,false);
	REP(s,0,N)
	{
		Reset();
		visited[s]=true; 
		REP(i,0,adj[s].size()) {nei=adj[s][i].ff; nxt[adj[s][i].ss].pb(nei);}
		newkeys.pb(r[s]); key[r[s]]=true;
		while(1>0)
		{
			if(newkeys.size()==0) {break;}
			REP(i,0,newkeys.size())
			{
				REP(j,0,nxt[newkeys[i]].size()) {DFS(nxt[newkeys[i]][j]);}
			}
			newkeys=newnewkeys; newnewkeys.clear();
		}
		REP(i,0,N) {if(visited[i]) {p[s]++;}}
	}
	ll me = *min_element(whole(p));
	vector<ll> ans; VV(ans,N,0); REP(i,0,N) {if(p[i]==me) {ans[i]=1;}}
	return ans;
}

Compilation message (stderr)

keys.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
keys.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

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