Submission #585174

#	Time	Username	Problem	Language	Result	Execution time	Memory
585174		TimDee	Game (IOI14_game)	C++14	15 / 100	4 ms	712 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;
    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]) {
            p[b]=a;
            q[a]+=q[b]-2;
            o[a]+=o[b]-1;
        } else {
            p[a]=b;
            q[b]+=q[a]-2;
            o[b]+=o[a]-1;
        }
        
    }

    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;
vector<set<int>> a;
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) {

  if (dsu.get(u)==dsu.get(v)) {
    return 1;
  } else {
    dsu.substract(u,v);
    a[u].erase(a[u].find(v));
    a[v].erase(a[v].find(u));
    int U=u;
    while (a[U].size()==1) {

      int V=*a[U].begin();
      a[V].erase(a[V].find(U));
      dsu.uni(U,V);
      a[U].clear();
      U=V;

    }
    U=v;
    while (a[U].size()==1) {
      int V=*a[U].begin();
      a[V].erase(a[V].find(U));
      dsu.uni(U,V);
      a[U].clear();
      U=V;
    }
    return 0;
  }

}

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