Submission #980714

#	Time	Username	Problem	Language	Result	Execution time	Memory
980714		nnin	Game (APIO22_game)	C++17	0 / 100	1 ms	2392 KiB

game

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

int n, k;
int dsu[600005]; //i: in (i), i+n: out (i)
int kk[600005];

int par(int x) {
  if(dsu[x]==x) return x;
  return dsu[x] = par(dsu[x]);
}

void init(int N, int K) {
  n = N; k = K;
  for(int i=0;i<2*n;i++) {
    dsu[i] = i;
  }
  for(int i=0;i<n;i++) {
    kk[i] = -2e9;
    kk[i+n] = 2e9;
  }
}

void join(int a, int b) {
  a = par(a);
  b = par(b);
  if(b%n<k) {
    if(a<n) kk[a] = max(kk[a], b%n);
    else kk[a] = min(kk[a], b%n);
  }
  if(a==b) return;
  if(a<n) kk[a] = max(kk[a], kk[b]);
  else kk[a] = min(kk[a], kk[b]);
}

int add_teleporter(int u, int v) {
  if((kk[par(u)]>=kk[par(u+n)] && abs(kk[par(u)])!=2e9) || (kk[par(v)]>=kk[par(v+n)] && abs(kk[par(v)])!=2e9)) return 1;
  if((par(u+n)-n<k && par(u+n)-n>=par(v))) return 1;
  join(u+n, v+n);
  join(v, u);
  dsu[par(v+n)] = par(u+n);
  dsu[par(u)] = par(v);
  return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40