Submission #744795

#TimeUsernameProblemLanguageResultExecution timeMemory
744795TeemkaGame (APIO22_game)C++17
0 / 100
5 ms9680 KiB
#include "bits/stdc++.h" #include "game.h" #define F first #define S second #define OK cout << "------OK---------" << endl; #define deb(x) cout << #x << " = " << x << endl; #define ll long long ; using namespace std ; const int N = 2e5 + 7; const int INF = 1e9 + 7 ; const int dx[4] = {0 , 1 , 0 , -1} , dy[4] = {1 , 0 , -1 , 0} ; int n , k , ok = 0 , mx[N] , mn[N]; vector<int > g[N] , rev[N] ; void dfs_mx(int v , int p){ if(mx[v] >= p) return ; mx[v] = p; if(mx[v] >= mn[v]){ ok = 1; return ; } for(int to : g[v]){ dfs_mx(to , p) ; } } void dfs_mn(int v , int p){ if(mn[v] <= p) return ; mn[v] = p; if(mx[v] >= mn[v]){ ok = 1; return ; } for(int to : rev[v]){ dfs_mn(to , p) ; } } void init(int _n, int _k) { n = _n , k = _k ; for(int i = 0 ; i< n; i ++){ mx[i] = -1 ; mn[i] = n ; } for(int i = 0; i< k - 1; i++){ mx[i + 1] = i ; mn[i] = i + 1 ; g[i].push_back(i + 1) ; rev[i + 1].push_back(i) ; } } int add_teleporter(int u, int v) { g[u].push_back(v) ; rev[v].push_back(u) ; if(u <= k - 1 and v <= k - 1) return 1; if(u <= k - 1){ dfs_mx(v , u) ; dfs_mn(u , mn[v]) ; } else if(v <= k - 1 ){ dfs_mx(v , mx[u]) ; dfs_mn(u , v) ; } else{ dfs_mx(v , mx[u]) ; dfs_mn(u , mn[v]) ; } return ok ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...