# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1205423 | bronze_coder | Permutation Game (APIO25_permgame) | C++20 | 2131 ms | 1051108 KiB |
#include "permgame.h"
#include <bits/stdc++.h>
using namespace std;
int Alice(int m, int e, vector<int> u, vector<int> v, int n, vector<int> p){
vector<int> degree(n,0);
for(int i:u){
degree[i]++;
}
for(int i:v){
degree[i]++;
}
int ans = 0;
for(int i=0;i<n;i++){
if(p[i]==i){
ans++;
}
}
for(int i:degree){
if(i>2){
return ans;
}
}
if(ans>n-m){
return ans;
}
vector<vector<int>> adj(m);
for(int i=0;i<e;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
vector<int> order;
for(int i=0;i<e;i++){
if(adj[i].size()==1||e==m){
order.push_back(i);
i = adj[i][0];
while(adj[i].size()==2){
order.push_back(i);
if(adj[i][0]==order[order.size()-2]){
i = adj[i][1];
}
else{
i = adj[i][0];
}
}
order.push_back(i);
break;
}
}
if(e==m-1){
while(ans<n-m+2-min(m-2,1)){
vector<int> visited(n,0);
vector<int> query(n);
int count = 0;
for(int i=0;i<n;i++){
if(p[i]!=i&&visited[i]==0&&query.size()<m){
int j = i;
while(visited[j]==0){
query[count] = j;
count++;
}
visited[i] = 1;
}
}
int t = Bob(query);
swap(p[u[t]],p[v[t]]);
ans = 0;
for(int i=0;i<n;i++){
if(p[i]==i){
ans++;
}
}
}
return n-m+2-min(m-2,1);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |