Submission #1205032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205032		irmuun	Permutation Game (APIO25_permgame)	C++20	22 / 100	17 ms	528 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=400;

vector<int>g[N];//initial graph/not P
vector<bool>vis(N);
vector<int>line;
vector<vector<int>>f;

void find(int x){
	line.pb(x);
	vis[x]=true;
	for(int y:g[x]){
		if(!vis[y]){
			find(y);
		}
	}
}

void dfs(int x){
	vis[x]=true;
	f.back().pb(x);
	for(int y:g[x]){
		if(!vis[y]){
			dfs(y);
		}
	}
}

int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p) {
	vector<int> t(m);
	if(m==2){
		for(int i=0;i<n;i++){
			if(p[i]!=i){
				for(int j=i+1;j<n;j++){
					if(p[j]==i){
						t[0]=i;
						t[1]=j;
						int j=Bob(t);
						swap(p[t[u[j]]], p[t[v[j]]]);
						break;
					}
				}
			}
		}
		return n;
	}
	int ans=0;
	for(int i=0;i<n;i++){
		if(p[i]==i){
			ans++;
		}
	}
	if(e>m){
		return ans;	
	}
	int start=ans;
	if(e==m-1){
		int deg=0;
		for(int i=0;i<e;i++){
			g[u[i]].pb(v[i]);
			g[v[i]].pb(u[i]);
		}
		for(int i=0;i<m;i++){
			deg=max(deg,(int)g[i].size());
		}
		if(deg>=3){
			return ans;
		}
		for(int i=0;i<m;i++){
			if(g[i].size()==1){
				find(i);
				break;
			}
		}
		int play=n*10;
		while(play--){
			fill(all(vis),false);
			for(int i=0;i<n;i++){
				g[i].clear();
			}
			f.clear();
			for(int i=0;i<n;i++){
				g[p[i]].pb(i);
				g[i].pb(p[i]);
			}
			for(int i=0;i<n;i++){
				if(!vis[i]){
					f.pb({});
					dfs(i);
				}
			}
			sort(all(f),[&](vector<int>a,vector<int>b){
				return (int)a.size()>(int)b.size();
			});
			vector<int>ord;
			for(int i=0;i<f.size();i++){
				for(int x:f[i]){
					ord.pb(x);
				}
			}
			for(int i=0;i<m;i++){
				t[line[i]]=ord[i];
			}
			int j=Bob(t);
			swap(p[t[u[j]]], p[t[v[j]]]);
			{
				int cnt=0;
				for(int i=0;i<n;i++){
					if(p[i]==i){
						cnt++;
					}
				}
				if(cnt>=max(n-m+1,start)){
					break;
				}
			}
		}
		return max(n-m+1,start);
	}
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24
• Subtask 6: 0 / 30