Submission #739849

#	Time	Username	Problem	Language	Result	Execution time	Memory
739849		dubabuba	Game (APIO22_game)	C++17	0 / 100	10 ms	15824 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 3e5 + 10;
const int mxm = 5e5 + 10;
vector<int> adj[mxn];
vector<int> rev[mxn];
int n, k;

int cnt_e[mxn], cnt_b[mxn];

vector<int> top;
void tsort() {
  int t[mxn];
  top.clear();

  queue<int> q;
  for(int i = 0; i < n; i++) {
    t[i] = cnt_e[i];
    if(t[i] == 0)
      q.push(i);
  }

  while(q.size()) {
    int u = q.front();
    top.push_back(u);
    q.pop();

    for(int v : adj[u]) {
      t[v]--;
      if(t[v] == 0)
        q.push(v);
    }
  }
}

void init(int N, int K) {
  n = N;
  k = K;
}

bool in_top[mxn];
int add_teleporter(int u, int v) {
  adj[u].push_back(v);
  rev[v].push_back(u);
  cnt_b[u]++;
  cnt_e[v]++;

  tsort();
  if(top.size() == n)
    return 0;

  memset(in_top, 0, sizeof in_top);
  for(int u : top)
    in_top[u] = 1;

  for(int i = 0; i < k; i++)
    if(!in_top[i])
      return 1;
  return 0;
}

Compilation message (stderr)

game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:52:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   if(top.size() == n)
      |      ~~~~~~~~~~~^~~~

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