Submission #1207042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207042		Ludissey	Permutation Game (APIO25_permgame)	C++20	6 / 100	0 ms	332 KiB

permgame

#include "permgame.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;



int Alice(int m, int e, std::vector<int> u, std::vector<int> v, int n, std::vector<int> p) {
    vector<vector<int>> neigh(m);
    for (int i = 0; i < e; i++)
    {
        neigh[u[i]].push_back(v[i]);
        neigh[v[i]].push_back(u[i]);
    }
    int sc=0;
    for (int i = 0; i < sz(p); i++) 
    {
        sc+=(p[i]==i);
    }
    vector<int> cnt(m);
    for (int i = 0; i < e; i++) { cnt[u[i]]++; cnt[v[i]]++; }
    int st=0;
    for (int i = 0; i < m; i++)
    {
        if(cnt[i]==1) {st=i; break; }
    }
    vector<int> tree;
    int pr=-1;
    while(sz(tree)<m){
        tree.push_back(st);
        bool br=false;
        for (auto ne : neigh[st])
        {
            if(pr==ne) continue;
            pr=st;
            st=ne;
            br=true;
            break;
        }
        if(!br) break;
    }
    if(sz(tree)!=m) return sc;
    bool b=true;
    while(b){
        b=false;
        for (int i = 0; i < n; i++)
        {
            int x=i;
            vector<int> visited(n,0);
            vector<int> q;
            while(!visited[x]&&sz(q)<m){
                visited[x]=true;
                q.push_back(x);
                x=p[x];
            }
            if(sz(q)==m){
                vector<int> t(m);
                for (int i = 0; i < m; i++)
                {
                    t[tree[i]]=q[i];
                }
                int j=Bob(t);
                swap(p[t[u[j]]],p[t[v[j]]]);
                b=true;
                break;
            }
        }
    }
    sc=0;
    
    for (int i = 0; i < n; i++) sc+=(p[i]==i);
    return sc;
}

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