Submission #612749

#	Time	Username	Problem	Language	Result	Execution time	Memory
612749		nohaxjustsoflo	Game (IOI14_game)	C++17	42 / 100	1088 ms	6540 KiB

game

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=3003;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const ll inf=1e18;
const int K=600;
int n;
set<pair<int,int>> s;
void initialize(int N)
{
    n=N;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            s.insert({i,j});
        }
    }
}
struct DSU
{
    vector<int> size,p;
    int comp;
    void build(int n)
    {
        size=vector<int>(n,1);
        p=vector<int>(n);
        iota(p.begin(),p.end(),0);
        comp=n;
    }
    int get(int x)
    {
        if(p[x]^x) p[x]=get(p[x]);
        return p[x];
    }
    bool unite(int a, int b)
    {
        a=get(a),b=get(b);
        if(a==b) return 0;
        if(size[a]>size[b]) swap(a,b);
        p[a]=b;
        size[b]+=size[a];
        comp--;
        return 1;
    }
};

int hasEdge(int u, int v)
{
   if(u>v) swap(u,v);
   s.erase({u,v});
   DSU dsu; dsu.build(n);
   for(auto par:s) dsu.unite(par.first,par.second);
   if(dsu.get(u)!=dsu.get(v))
   {
       s.insert({u,v});
       return 1;
   }
   return 0;
}

/*
7 3
4 1 3 4 0 2 3
*/

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