Submission #788193

#	Time	Username	Problem	Language	Result	Execution time	Memory
788193		yeyso	Game (APIO22_game)	C++17	0 / 100	23 ms	39992 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// First special node that can be reached from index i
vector<int> f;
// Last special node that can reach index i
vector<int> l;
int K;
vector<vector<int>> adj;
vector<vector<int>> radj;
const int MAXM = 5e3+5;
const int MAXK = 1e3+5;
vector<vector<int>> visited(10005, vector<int>(1005, 0));
vector<int> pv;

void dfs_forward(int u, int a, int x){
  if(!visited[x][u]){
    visited[x][u] = 1;
    //cout << u << " ";
    if(u < K) f[a] = min(f[a], u);
    for(int i = 0; i < adj[u].size(); i ++){
        dfs_forward(adj[u][i], a, x);
    }
  }
}
void dfs_backward(int u, int a, int x){
  if(!visited[x][u]){
    visited[x][u] = 1;
    //cout << u << " ";
    if(u < K) l[a] = max(l[a], u);
    for(int i = 0; i < radj[u].size(); i ++){
        dfs_backward(radj[u][i], a, x);
    }
  }
}
int x = 0;
void init(int n, int k) {
    K = k;
    f.resize(n, INT_MAX / 2);
    l.resize(n, -1);
    for(int i = 0; i < k - 1; i ++) f[i] = i + 1;
    for(int i = 1; i < k; i ++) l[i] = i - 1;

    vector<vector<int>> adj0(n, vector<int>());
    adj = adj0; radj = adj0;
}

int add_teleporter(int u, int v) {

    adj[u].push_back(v);
    radj[v].push_back(u);

    dfs_forward(u, u, x);
    //cout << "\n";
    dfs_backward(u, u, x + 1);
    x += 2;

    if(f[u] <= l[u]) return 1;
    return 0;
}
/*
g++ -Wall -lm -static -DEVAL -o game -O2 game.cpp grader.cpp -std=c++17
6 5 3
3 4
4 5
5 3
5 1
2 3

*/

Compilation message (stderr)

game.cpp: In function 'void dfs_forward(int, int, int)':
game.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0; i < adj[u].size(); i ++){
      |                    ~~^~~~~~~~~~~~~~~
game.cpp: In function 'void dfs_backward(int, int, int)':
game.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i < radj[u].size(); i ++){
      |                    ~~^~~~~~~~~~~~~~~~

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