| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 773472 |
2023-07-05T05:52:10 Z |
LittleCube |
Game (APIO22_game) |
C++17 |
|
105 ms |
262144 KB |
#pragma GCC optimize("Ofast,unroll-loops")
#include "game.h"
#ifndef EVAL
#include "game_grader.cpp"
#endif
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
namespace
{
int n, k, from[300000][20], to[300000][20], where[300000][20];
vector<int> Ef[300000][20], Et[300000][20];
void update_from(int u, int layer, vector<int> &same)
{
if (from[u][layer] == to[u][layer])
same.emplace_back(u);
for (auto v : Ef[u][layer])
if (from[u][layer] > from[v][layer])
{
from[v][layer] = from[u][layer];
update_from(v, layer, same);
}
}
void update_to(int u, int layer, vector<int> &same)
{
if (from[u][layer] == to[u][layer])
same.emplace_back(u);
for (auto v : Et[u][layer])
if (to[u][layer] < to[v][layer])
{
to[v][layer] = to[u][layer];
update_to(v, layer, same);
}
}
void build(int i = 1, int L = 0, int R = k - 1, int l = 0)
{
for (int j = L; j <= R; j++)
where[j][l] = i;
if (L != R)
{
int mid = (L + R) / 2;
for (int j = L; j <= mid; j++)
from[j][l] = to[j][l] = 1;
for (int j = mid + 1; j <= R; j++)
from[j][l] = to[j][l] = 2;
build(i << 1, L, mid, l + 1);
build(i << 1 | 1, mid + 1, R, l + 1);
}
else
from[L][l] = 2, to[L][l] = 1;
}
int add_edge(int, int, int, int);
int add_node(int u, int i, int l)
{
if (where[u][l])
return 0;
where[u][l] = i;
from[u][l] = 0, to[u][l] = 3;
bool flag = 0;
for (auto v : Et[u][l - 1])
if (where[u][l] == where[v][l])
flag |= add_edge(v, u, i, l);
for (auto v : Ef[u][l - 1])
if (where[u][l] == where[v][l])
flag |= add_edge(u, v, i, l);
return flag | (from[u][l] > to[u][l]);
}
int add_edge(int u, int v, int i = 1, int l = 0)
{
Ef[u][l].emplace_back(v);
Et[v][l].emplace_back(u);
from[v][l] = max(from[v][l], from[u][l]);
to[u][l] = min(to[u][l], to[v][l]);
vector<int> s;
bool flag = 0;
if (v >= k)
{
update_from(v, l, s);
flag |= (from[v][l] > to[v][l]);
}
if (u >= k)
{
update_to(u, l, s);
flag |= (from[u][l] > to[u][l]);
}
for (int w : s)
if (from[w][l] == 1)
flag |= add_node(w, i << 1, l + 1);
else
flag |= add_node(w, i << 1 | 1, l + 1);
return flag;
}
}
void init(int n, int k)
{
::n = n, ::k = k;
build();
for (int i = k; i < n; i++)
{
from[i][0] = 0, to[i][0] = 3;
where[i][0] = 1;
}
}
int add_teleporter(int u, int v)
{
if (u < k && v < k)
{
if (v <= u)
return 1;
return 0;
}
bool ans = add_edge(u, v);
// for (int p = 0; p < 5; p++)
// for (int i = 0; i < n; i++)
// cout << from[i][p] << ' ' << to[i][p] << ' ' << " \n"[i == n - 1];
// cout << '\n';
// for (int p = 0; p < 5; p++)
// for (int i = 0; i < n; i++)
// cout << where[i][p] << " \n"[i == n - 1];
// ;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
105 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
105 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
105 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
105 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
105 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
