oj.uz

Submission #788201

# Submission time Handle Problem Language Result Execution time Memory
788201 2023-07-19T23:03:28 Z yeyso Game (APIO22_game) C++17
0 / 100
 22 ms 39956 KB 
#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;
    //cout << f[u] << " " << l[u]  << " | " << u << "\n";
    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

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.0 / 2.0

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

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 18.0

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

Subtask #4
0.0 / 30.0

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

Subtask #5
0.0 / 40.0

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