Submission #1130909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130909		79brue	Magic Show (APIO24_show)	C++20	100 / 100	916 ms	198360 KiB

Alice

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

using namespace std;

typedef long long ll;

namespace {
    struct Edge{
        int x, y;
        Edge(){}
        Edge(int x, int y): x(x), y(y){}
    };

    const int n = 5000, k = 60;
    vector<Edge> vec[k];

    void init(){
        for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++){
            vec[rand()%k].push_back(Edge(i, j));
        }
    }

    struct unionFind{
        int par[5002];

        void init(int n){
            for(int i=1; i<=n; i++) par[i] = i;
        }

        int find(int x){
            if(x==par[x]) return x;
            return par[x] = find(par[x]);
        }

        void merge(int x, int y){
            x=find(x), y=find(y);
            par[x] = y;
        }
    } dsu;

    vector<pair<int, int> > ans;
}

vector<pair<int,int> > Alice(){
    init();

    ll X = setN(n);
    vector<int> v;
    for(int d=0; d<k; d++) if((X>>d)&1) v.push_back(d);

    dsu.init(n);

    int pnt = 0, m = 0;
    while(m < n-1){
        int x = v[pnt];
        while(!vec[x].empty()){
            int a = vec[x].back().x, b = vec[x].back().y;
            vec[x].pop_back();
            if(dsu.find(a) == dsu.find(b)) continue;
            dsu.merge(a, b), m++, ans.push_back(make_pair(a, b));
//            printf("%d\n", m);
            break;
        }
        pnt = (pnt + 1) % (int)v.size();
    }

    return ans;
}

Bob

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

using namespace std;

typedef long long ll;

namespace {
    struct Edge{
        int x, y;
        Edge(){}
        Edge(int x, int y): x(x), y(y){}
    };

    const int n = 5000, k = 60;
    int where[5002][5002];
    vector<Edge> vec[k];

    void init(){
        for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++){
            int w = rand()%k;
            vec[w].push_back(Edge(i, j));
            where[i][j] = where[j][i] = w;
        }
    }
}

ll Bob(vector<pair<int,int>> V){
    init();

    ll X = 0;
    for(auto [x, y]: V) X |= 1LL << where[x][y];
    return X;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65