Submission #601047

#	Time	Username	Problem	Language	Result	Execution time	Memory
601047		vanic	Amusement Park (CEOI19_amusementpark)	C++14	42 / 100	2714 ms	227792 KiB

amusementpark

#include <cstdio>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;

const int maxm=45, maxn=10;

pair < int, int > edg[maxm];
int n, m;
int sol;
map < ll, bool > bio;
int red[maxn];

void probaj(){
	ll tren=0;
	for(int i=0; i<m; i++){
		if(red[edg[i].second]<red[edg[i].first]){
			tren+=(1ll<<i);
		}
	}
	if(!bio[tren]){
		bio[tren]=1;
		sol+=__builtin_popcountll(tren);
	}
}

void scan(int &a){
	a=0;
	char c=getchar_unlocked();
	while(c>='0' && c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar_unlocked();
	}
}

queue < int > ost;

void rek(int x){
	if(x==n){
		probaj();
		return;
	}
	for(int i=0; i<n-x; i++){
		red[x]=ost.front();
		ost.pop();
		rek(x+1);
		ost.push(red[x]);
	}
}


int main(){
	scan(n);
	scan(m);
	assert(n<=maxn);
	for(int i=0; i<m; i++){
		scan(edg[i].first);
		scan(edg[i].second);
		edg[i].first--;
		edg[i].second--;
	}
	for(int i=0; i<n; i++){
		ost.push(i);
	}
	rek(0);
	printf("%d\n", sol);
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37