Submission #72036

#	Time	Username	Problem	Language	Result	Execution time	Memory
72036		The quick brown fox jumps over the lazy dog (#118)	Key of Impassable Doors (FXCUP3_key)	C++17	100 / 100	115 ms	5164 KiB

key

#include "key.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef pair<int,int> pii;

const int N = 1005;

int n, par[N], cyc[N], cs[N], cc;
pii ord[N];

bool vis[N];

vector<int> ci[N];

int dfs (int I) {
	if(vis[I]) return 0;
	if(cyc[I]) {
		for(auto &T : ci[cyc[I]]) {
			vis[T] = true;
		}
		return cs[cyc[I]];
	}
	else {
		vis[I] = true;
		return dfs(par[I]) + 1;
	}
}

int Try (vector<int> &V) {
	fill(vis+1, vis+1+n, false);
	int R = 0;
	for(auto &T : V) {
		R += dfs(T);
	}
	return R;
}

void EnsureKeyInfo(int _N) {
	n = _N;
	for(int i=1;i<=n;i++) {
		TakeKey(i);
		int T = Explore();
		ord[i] = {T, i};
	}
	sort(ord+1, ord+1+n);
	for(int i=1;i<=n;i++) {
		if(ord[i].X == 1) {
			cyc[ord[i].Y] = ++cc;
			cs[cc] = 1;
			ci[cc].push_back(ord[i].Y);
			continue;
		}
		int S = 1, E = i;
		bool inc = false;
		while(S<E) {
			int M = (S+E)/2;
			vector<int> V;
			for(int j=1;j<=M;j++) {
				V.push_back(ord[j].Y);
				TakeKey(ord[j].Y);
			}
			TakeKey(ord[i].Y);
			int A = Try(V), B = Explore();
			if(B - A == 0) inc = true;
			if(B - A <= 1) E = M;
			else S = M+1;
		}
		if(S == i) {
			cyc[ord[i].Y] = ++cc;
			cs[cc] = ord[i].X;
			ci[cc].push_back(ord[i].Y);
			continue;
		}
		else if(inc) {
			cyc[ord[i].Y] = cyc[ord[S].Y];
			ci[cyc[ord[S].Y]].push_back(ord[i].Y);
		}
		else par[ord[i].Y] = ord[S].Y;
	}
	for(int i=1;i<=n;i++) {
		fill(vis+1, vis+1+n, false);
		dfs(i);
		for(int j=1;j<=n;j++) {
			if(vis[j]) Report(i, j);
		}
	}
}

• Subtask 1: 23 / 23
• Subtask 2: 34 / 34
• Subtask 3: 43 / 43