oj.uz

Submission #980714

# Submission time Handle Problem Language Result Execution time Memory
980714 2024-05-12T10:48:41 Z nnin Game (APIO22_game) C++17
0 / 100
 1 ms 2392 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Wrong Answer[1]
3 Halted 0 ms 0 KB -