Submission #585176

#	Time	Username	Problem	Language	Result	Execution time	Memory
585176		TimDee	Game (IOI14_game)	C++14	0 / 100	1 ms	340 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define forn(i,n) for (int i=0; i<n; ++i) 

vector<set<int>> A;

struct DSU {
 
    vector<int> p;
    vector<int> r;
    vector<int> q;
    vector<int> o;
    
    DSU(int n) {
        p.assign(n,0);
        r.assign(n,0);
        forn(i,n) p[i]=i;
        q.assign(n,n-1);
        o.assign(n,0);
    }
    
    int get(int i) {
           
        return p[i]==i ? i : get(p[i]);
        
    }
    
    void uni(int a, int b) {
        
        a=get(a);
        b=get(b);
        if (a==b) return;
        
        if (r[a]==r[b]) r[a]++;
        
        if (r[a]>r[b]) {
            swap(a,b);
        }

        p[a]=b;
        q[b]+=q[a]-2;
        o[b]+=o[a]-1;

        while (A[a].size()) {
          A[b].insert(*A[a].begin());
          A[a].erase(A[a].begin());
        }
    }

    void substract(int a, int b) {
      a=get(a);
      b=get(b);
      --q[a];
      --q[b];
    }

    int getq(int a) {
      a=get(a);
      return q[a];
    }

    int geto(int a) {
      a=get(a);
      return o[a];
    }

    void inco(int a) {
      a=get(a);
      o[a]++;
    }
    
};

DSU dsu(0);
int q;
int n;

void initialize(int N) {
  n=N;
  DSU paiu(n);
  dsu=paiu;
  q=n*(n-1)/2;
  A.resize(n);
  forn(i,n) forn(j,n) if (i!=j) A[i].insert(j);
  //cout<<"!"<<dsu.p.size()<<'\n';
}

int hasEdge(int u, int v) {

  u=dsu.get(u), v=dsu.get(v);
  if (u==v) {
    return 1;
  } else {
    dsu.substract(u,v);
    A[u].erase(A[u].find(v));
    A[v].erase(A[v].find(u));
    if (A[u].size()==1) {
      int V=*A[u].begin();
      A[u].clear();
      A[V].erase(u);
      dsu.uni(u,V);
      u=V;
    }
    if (A[v].size()==1) {
      int V=*A[v].begin();
      A[v].clear();
      A[V].erase(v);
      dsu.uni(v,V);
      v=V;
    }
    return 0;
  }

}

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