| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 744842 |
2023-05-19T06:48:13 Z |
Nahian9696 |
Game (APIO22_game) |
C++17 |
|
2 ms |
4432 KB |
#include "game.h"
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int32_t> vi;
typedef vector<ll> vll;
typedef pair<int32_t, int32_t> pii;
#define endl "\n"
#define f0(i,n) for(int32_t i = 0; i < (n); i++)
#define f1(i,n) for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r) for(int32_t i=(l); i < (r); i++)
#define rep1(i,l,r) for(int32_t i=(l); i <= (r); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define asrt(v) sort(all(v))
#define dsrt(v) sort(rall(v))
#define revStr(str) string(rall(str))
#define len(a) ((int64_t)(a).size())
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcountll(n)
#define lcm(a, b) (((a)*(b))/gcd(a,b))
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define pf push_front
#define mp make_pair
#define ff first
#define ss second
#define finish return 0
#define clean fflush(stdout)
#define Inf (int32_t)(1e9)
#define INF (lli)(1e18)
#define Eps (ld)(1e-9)
#define EPS (ld)(1e-18)
#define PI (ld)(3.141592653589793238462643383279502884197169L)
#define MOD (int32_t)(1e9+7)
#define MXN (int32_t)(1e5+7)
template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}
int n, k;
vi grph[30005], invgrph[30005];
// bool fr[30005][1003], t[30005][1003];
set<int> from[30005], to[30005];
void init(int N, int K) {
n = N;
k = K;
}
int add_teleporter(int u, int v) {
if((u < k) && (v < k)) {
if(u == v) return 1;
if(u > k) {
// print(u, v, "u < v");
return 1;
}
else return 0;
}
if(u == v) return 0;
if(u < k) {
if(to[v].size()) {
int mn = *(to[v].begin());
if(mn <= u) return 1;
}
auto it = from[v].find(u);
if(it == from[v].end()) {
queue<int> q;
q.push(v);
while(!q.empty()) {
int cur = q.front();
q.pop();
from[cur].insert(u);
for(int nxt: grph[cur]) {
if(nxt < k) continue;
auto it = from[nxt].find(u);
if(it == from[nxt].end()) {
q.push(nxt);
}
}
}
}
grph[u].pb(v);
invgrph[v].pb(u);
}
if(v < k) {
if(from[u].size()) {
int mx = *prev(from[u].end());
if(mx >= v) return 1;
}
auto it = to[u].find(v);
if(it == to[u].end()) {
queue<int> q;
q.push(u);
while(!q.empty()) {
int cur = q.front();
q.pop();
to[cur].insert(v);
for(int nxt: invgrph[cur]) {
if(nxt < k) continue;
auto it = to[nxt].find(v);
if(it == to[nxt].end()) {
q.push(nxt);
}
}
}
}
grph[u].pb(v);
invgrph[v].pb(u);
}
// int U = u, V = v;
for(int uu: from[u]) {
if(to[v].size()) {
int mn = *(to[v].begin());
if(mn <= uu) return 1;
}
auto it = from[v].find(uu);
if(it == from[v].end()) {
queue<int> q;
q.push(v);
while(!q.empty()) {
int cur = q.front();
q.pop();
from[cur].insert(uu);
for(int nxt: grph[cur]) {
if(nxt < k) continue;
auto it = from[nxt].find(uu);
if(it == from[nxt].end()) {
q.push(nxt);
}
}
}
}
}
for(int vv: to[v]) {
if(from[u].size()) {
int mx = *prev(from[u].end());
if(mx >= vv) return 1;
}
auto it = to[u].find(vv);
if(it == to[u].end()) {
queue<int> q;
q.push(u);
while(!q.empty()) {
int cur = q.front();
q.pop();
to[cur].insert(vv);
for(int nxt: invgrph[cur]) {
if(nxt < k) continue;
auto it = to[nxt].find(vv);
if(it == to[nxt].end()) {
q.push(nxt);
}
}
}
}
}
grph[u].pb(v);
invgrph[v].pb(u);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4432 KB |
Wrong Answer[1] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4432 KB |
Wrong Answer[1] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4432 KB |
Wrong Answer[1] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4432 KB |
Wrong Answer[1] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4432 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
4432 KB |
Wrong Answer[1] |
| 5 |
Halted |
0 ms |
0 KB |
- |
