제출 #584718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584718		TimDee	게임 (IOI14_game)	C++14	15 / 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) 

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 (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) {

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

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

  //cout<<u<<' '<<v<<' '<<U<<' '<<V<<' '<<A<<' '<<B<<'\n';

  if (U==A+1 || V==B+1) {
    dsu.uni(u,v);
    a[u].erase(a[u].find(v));
    a[v].erase(a[v].find(u));
    
    if (dsu.getq(u)==1) {
      forn(i,n) {
        if (a[i].find(u)!=a[i].end()) {
          dsu.inco(i);
        }
        if (a[i].find(v)!=a[i].end()) {
          dsu.inco(i);
        }
      }
    }
    return 1;
  } else {
    dsu.substract(u,v);
    a[u].erase(a[u].find(v));
    a[v].erase(a[v].find(u));
    if (dsu.getq(u)==1) {
      forn(i,n) {
        if (a[i].find(u)!=a[i].end()) {
          //cout<<"one in "<<u<<' '<<i<<'\n';
          dsu.inco(i);
        }
      }
    }
    if (dsu.get(u)!=dsu.get(v) && dsu.getq(v)==1) {
      forn(i,n) {
        if (a[i].find(v)!=a[i].end()) {
          dsu.inco(i);
          //cout<<"one in "<<v<<' '<<i<<'\n';
        }
      }
    }
    return 0;
  }

}

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