Submission #584703

#	Time	Username	Problem	Language	Result	Execution time	Memory
584703		TimDee	Game (IOI14_game)	C++14	15 / 100	2 ms	312 KiB

game

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

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

struct DSU {
 
    vector<int> p;
    vector<int> r;
    vector<int> q;
    
    DSU(int n) {
        p.assign(n,0);
        r.assign(n,0);
        forn(i,n) p[i]=i;
        q.assign(n,n-1);
    }
    
    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 (r[a]==r[b]) r[a]++;
        
        if (r[a]>r[b]) {
            p[b]=a;
            q[a]+=q[b]-2;
        } else {
            p[a]=b;
            q[b]+=q[a]-2;
        }
        
    }

    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];
    }
    
};

DSU dsu(0);
int q;

void initialize(int n) {
  DSU paiu(n);
  dsu=paiu;
  q=n*(n-1)/2;
  //cout<<"!"<<dsu.p.size()<<'\n';
}

int hasEdge(int u, int v) {

  --q;
  if (q==1) {
    return 0;
  }
  if (q==0) {
    return 1;
  }

  int U=dsu.getq(u);
  int V=dsu.getq(v);

  if (U<=2 || V<=2) {
    dsu.uni(u,v);
    return 1;
  } else {
    dsu.substract(u,v);
    return 0;
  }

}

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