Submission #1133755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133755		t9unkubj	Game (IOI14_game)	C++20	42 / 100	1098 ms	185524 KiB

game

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;

template<class T,auto op,int extra>
struct base_dsu{
        vector<int>par;
        vector<T>data;
        base_dsu(int n):par(n,-1){
            static_assert(!extra,"e is needed");
        }
        base_dsu(int n,T e):par(n,-1),data(n,e){}
        T& operator[](int i){
            static_assert(extra,"No data");
            return data[leader(i)];
        }
        int root(int x){
            if(par[x]<0)return x;
            else return par[x]=root(par[x]);
        }
        bool same(int x,int y){
            return root(x)==root(y);
        }
        bool merge(int x,int y){
            x=root(x);
            y=root(y);
            if(x==y)return false;
            par[x]+=par[y];
            par[y]=x;
            return true;
        }
        int size(int x){
            return -par[root(x)];
        }
        int leader(int x){
            return root(x);
        }

};
int tf323(int a,int b){return a;}
using dsu=base_dsu<int,tf323,0>;
template<class T,auto op>
using extra_dsu=base_dsu<T,op,1>;

constexpr int N=1500;
dsu ds(N);
int cnt[N][N];
unordered_multiset<int>edge[N];

void initialize(int n) {
    ds=dsu(N);
    rep(i,N)rep(j,N)cnt[i][j]=0;
    rep(i,N)edge[i].clear();
}
int hasEdge(int u, int v) {
    u=ds.root(u),v=ds.root(v);
    assert(u!=v);
    if(cnt[u][v]==ds.size(u)*ds.size(v)-1){
        if(edge[u].size()<edge[v].size())swap(u,v);
        for(auto&x:edge[v]){
            if(ds.same(x,v)||ds.same(x,u))continue;
            assert(x==ds.root(x));
            edge[u].insert(x);
            cnt[u][x]++;

            cnt[x][u]++;
            edge[x].erase(edge[x].find(v));
            edge[x].insert(u);
        }
        ds.merge(u,v);
        return 1;
    }else{
        edge[u].insert(v);
        edge[v].insert(u);
        cnt[u][v]++,cnt[v][u]++;
        return 0;
    }
}
mt19937 mt(2);
namespace judge{
    void run(){
    while(1){
        int n=5;
        initialize(n);
        vc<pair<int,int>>edge;
        rep(i,n)REP(j,i+1,n)edge.push_back({i,j});
        shuffle(all(edge),mt);
        dbg(edge);
        for(auto&[x,y]:edge)dbg(x,y),dbg(hasEdge(x,y));
    }
    }
};
//int main(){judge::run();}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58