oj.uz

Submission #978678

# Submission time Handle Problem Language Result Execution time Memory
978678 2024-05-09T13:25:00 Z hocln Game (APIO22_game) C++17
30 / 100
 4000 ms 9932 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
const long long MOD = 1e9 + 7;
//const long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;
const int N = 3e5 + 15;
bool vis[N],vis2[N];
vector<int>adj[N];
int n, k;
void init(int _n, int _k) {
	n = _n;
	k = _k;
	for(int i = 0;i < n;i++) adj[i].clear();
	for(int i = 0;i < k-1;i++) adj[i].emplace_back(i+1);
}
 
inline bool bad(int a) {
	vis2[a] = true;
	vis[a] = true;
	bool ok = false;
	for(auto& i : adj[a]) {
		if(vis2[i] && i < k) {
          ok = true;
          break;
        }
		if(!vis[i]) ok |= bad(i);
	}
	vis2[a] = false;
	return ok;
}
 
int add_teleporter(int a, int b) {
	for(int i = 0;i < n;i++) vis[i] = vis2[i] = false;
	if(a == b && a < k) return true;
	adj[a].emplace_back(b);
	for(int i = 0;i < k;i++) {
		if(!vis[i] && bad(i)) return true;
	}
	return false;
}
//inline void solve_test() {
	//init(4,2);
	//cout << add_teleporter(1,1);
//}
 
//int main()
//{
    ////srand(chrono::steady_clock::now().time_since_epoch().count());
    ////freopen("convention2.in", "r", stdin);
    ////freopen("convention2.out", "w", stdout);
	////cout << "Case #" << tc << ": " << ans << '\n';
	////cout << fixed << setprecision(7);
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    //int tt = 1;
    ////cin >> tt;
    //while(tt--) {
		//++tc;
        //solve_test();
    //}
//}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 3 ms 7256 KB Output is correct
9 Correct 2 ms 7252 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 3 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7276 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 3 ms 7256 KB Output is correct
9 Correct 2 ms 7252 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 3 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7276 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 2 ms 7512 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 3 ms 7512 KB Output is correct
23 Correct 2 ms 7512 KB Output is correct
24 Correct 9 ms 7512 KB Output is correct
25 Correct 28 ms 7796 KB Output is correct
26 Correct 31 ms 8024 KB Output is correct
27 Correct 36 ms 7800 KB Output is correct
28 Correct 15 ms 7512 KB Output is correct
29 Correct 29 ms 7544 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 3 ms 7256 KB Output is correct
9 Correct 2 ms 7252 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 3 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7276 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 2 ms 7512 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 3 ms 7512 KB Output is correct
23 Correct 2 ms 7512 KB Output is correct
24 Correct 9 ms 7512 KB Output is correct
25 Correct 28 ms 7796 KB Output is correct
26 Correct 31 ms 8024 KB Output is correct
27 Correct 36 ms 7800 KB Output is correct
28 Correct 15 ms 7512 KB Output is correct
29 Correct 29 ms 7544 KB Output is correct
30 Correct 107 ms 8516 KB Output is correct
31 Correct 70 ms 7984 KB Output is correct
32 Correct 75 ms 9372 KB Output is correct
33 Correct 44 ms 8756 KB Output is correct
34 Correct 1114 ms 9932 KB Output is correct
35 Execution timed out 4033 ms 8684 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7256 KB Output is correct
3 Correct 2 ms 7256 KB Output is correct
4 Correct 2 ms 7256 KB Output is correct
5 Correct 2 ms 7256 KB Output is correct
6 Correct 2 ms 7256 KB Output is correct
7 Correct 2 ms 7256 KB Output is correct
8 Correct 3 ms 7256 KB Output is correct
9 Correct 2 ms 7252 KB Output is correct
10 Correct 2 ms 7256 KB Output is correct
11 Correct 3 ms 7256 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 2 ms 7256 KB Output is correct
14 Correct 2 ms 7256 KB Output is correct
15 Correct 2 ms 7256 KB Output is correct
16 Correct 2 ms 7276 KB Output is correct
17 Correct 2 ms 7256 KB Output is correct
18 Correct 2 ms 7256 KB Output is correct
19 Correct 2 ms 7256 KB Output is correct
20 Correct 2 ms 7512 KB Output is correct
21 Correct 2 ms 7256 KB Output is correct
22 Correct 3 ms 7512 KB Output is correct
23 Correct 2 ms 7512 KB Output is correct
24 Correct 9 ms 7512 KB Output is correct
25 Correct 28 ms 7796 KB Output is correct
26 Correct 31 ms 8024 KB Output is correct
27 Correct 36 ms 7800 KB Output is correct
28 Correct 15 ms 7512 KB Output is correct
29 Correct 29 ms 7544 KB Output is correct
30 Correct 107 ms 8516 KB Output is correct
31 Correct 70 ms 7984 KB Output is correct
32 Correct 75 ms 9372 KB Output is correct
33 Correct 44 ms 8756 KB Output is correct
34 Correct 1114 ms 9932 KB Output is correct
35 Execution timed out 4033 ms 8684 KB Time limit exceeded
36 Halted 0 ms 0 KB -