Submission #918060

#	Time	Username	Problem	Language	Result	Execution time	Memory
918060		waldi	Monster Game (JOI21_monster)	C++17	10 / 100	134 ms	3768 KiB

monster

#include <bits/stdc++.h>
#include "monster.h"
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int(x.size()))
#define all(x) (x).begin(),(x).end()
using namespace std;

int tab[1000][1000];
bool zapytaj(int a, int b){
	if(a > b) return (tab[a][b] = 1+(!zapytaj(b, a)))-1;
	if(!tab[a][b]) tab[a][b] = 1+Query(a, b);
	return tab[a][b]-1;
}

vector<int> Solve(int n){
	vector<int> ret(n);
	
	REP(i, n) REP(j, n) if(i != j) zapytaj(i, j);
	REP(i, n) REP(j, n) if(i != j) tab[i][j] = tab[i][j]-1 ? 1 : n;
	REP(k, n) REP(i, n) REP(j, n) tab[i][j] = min(tab[i][j], tab[i][k]+tab[k][j]);
	
	int poc = -1, kon = -1;
	REP(i, n) REP(j, n) if(tab[i][j] == n-1) poc = i, kon = j;
	
	REP(i, n){
		ret[poc] = i;
		REP(j, n) if(tab[poc][j]==1 && tab[j][kon] == n-i-2){poc = j; break;}
	}
	return ret;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75