# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1063694 |
2024-08-17T23:35:43 Z |
pawned |
Game (IOI14_game) |
C++17 |
|
13 ms |
18232 KB |
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "game.h"
struct DSU {
vi e;
void init(int N) {
e = vi(N, -1);
}
int root(int x) {
if (e[x] < 0) {
return x;
}
else {
e[x] = root(e[x]);
return e[x];
}
}
bool sameset(int x, int y) {
return(root(x) == root(y));
}
bool merge(int x, int y) {
x = root(x);
y = root(y);
if (x == y)
return false;
if (-e[x] < -e[y])
swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
int size(int x) {
return -e[root(x)];
}
};
const int MAX = 1505;
int N;
DSU dsu;
int ccs;
vector<vi> adj(MAX, vi(MAX, 0));
// 0 if not done
// 1 if missing
// 2 if filled
void initialize(int n) {
N = n;
dsu.init(N);
ccs = N;
}
int hasEdge(int u, int v) {
/* cout<<"adj: "<<endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout<<adj[i][j]<<" ";
}
cout<<endl;
}
cout<<"ccs: "<<ccs<<endl;*/
// check if connecting u to v makes any "bad triangle"
// bad triangle u, v, w if (u, v) = 2, (u, w) = 2, and (v, w) isn't 1
// or if (v, w) = 2 and (u, w) isn't 1
bool can = true;
for (int i = 0; i < N; i++) {
if (adj[u][i] == 2 && adj[v][i] != 1)
can = false;
if (adj[v][i] == 2 && adj[u][i] != 1)
can = false;
}
if (can && ccs >= 3) {
adj[u][v] = 2;
adj[v][u] = 2;
if (!dsu.sameset(u, v)) {
dsu.merge(u, v);
ccs--;
}
return 1;
}
else {
adj[u][v] = 1;
adj[v][u] = 1;
return 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
18008 KB |
Output is correct |
2 |
Correct |
9 ms |
18224 KB |
Output is correct |
3 |
Correct |
9 ms |
18008 KB |
Output is correct |
4 |
Correct |
9 ms |
18012 KB |
Output is correct |
5 |
Correct |
8 ms |
18012 KB |
Output is correct |
6 |
Correct |
8 ms |
18128 KB |
Output is correct |
7 |
Correct |
12 ms |
18012 KB |
Output is correct |
8 |
Correct |
8 ms |
18008 KB |
Output is correct |
9 |
Correct |
10 ms |
18012 KB |
Output is correct |
10 |
Correct |
8 ms |
18100 KB |
Output is correct |
11 |
Correct |
7 ms |
18012 KB |
Output is correct |
12 |
Correct |
8 ms |
18012 KB |
Output is correct |
13 |
Correct |
8 ms |
18012 KB |
Output is correct |
14 |
Correct |
8 ms |
18012 KB |
Output is correct |
15 |
Correct |
8 ms |
18012 KB |
Output is correct |
16 |
Correct |
8 ms |
17992 KB |
Output is correct |
17 |
Correct |
9 ms |
18012 KB |
Output is correct |
18 |
Correct |
9 ms |
18012 KB |
Output is correct |
19 |
Correct |
8 ms |
18012 KB |
Output is correct |
20 |
Correct |
8 ms |
17976 KB |
Output is correct |
21 |
Correct |
8 ms |
18012 KB |
Output is correct |
22 |
Correct |
8 ms |
18012 KB |
Output is correct |
23 |
Correct |
7 ms |
18012 KB |
Output is correct |
24 |
Correct |
9 ms |
18012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
18008 KB |
Output is correct |
2 |
Correct |
11 ms |
18020 KB |
Output is correct |
3 |
Correct |
9 ms |
18012 KB |
Output is correct |
4 |
Correct |
8 ms |
18180 KB |
Output is correct |
5 |
Correct |
8 ms |
18012 KB |
Output is correct |
6 |
Correct |
8 ms |
18132 KB |
Output is correct |
7 |
Correct |
7 ms |
18012 KB |
Output is correct |
8 |
Correct |
8 ms |
18012 KB |
Output is correct |
9 |
Correct |
9 ms |
18012 KB |
Output is correct |
10 |
Correct |
9 ms |
18012 KB |
Output is correct |
11 |
Correct |
9 ms |
18012 KB |
Output is correct |
12 |
Correct |
8 ms |
18172 KB |
Output is correct |
13 |
Correct |
8 ms |
18136 KB |
Output is correct |
14 |
Correct |
8 ms |
18012 KB |
Output is correct |
15 |
Correct |
9 ms |
18012 KB |
Output is correct |
16 |
Correct |
8 ms |
17976 KB |
Output is correct |
17 |
Correct |
8 ms |
18012 KB |
Output is correct |
18 |
Correct |
8 ms |
18008 KB |
Output is correct |
19 |
Correct |
8 ms |
18012 KB |
Output is correct |
20 |
Correct |
8 ms |
17972 KB |
Output is correct |
21 |
Correct |
8 ms |
18008 KB |
Output is correct |
22 |
Correct |
8 ms |
18012 KB |
Output is correct |
23 |
Correct |
7 ms |
18108 KB |
Output is correct |
24 |
Correct |
8 ms |
18012 KB |
Output is correct |
25 |
Incorrect |
8 ms |
18012 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
18012 KB |
Output is correct |
2 |
Correct |
7 ms |
18012 KB |
Output is correct |
3 |
Correct |
8 ms |
18012 KB |
Output is correct |
4 |
Correct |
8 ms |
18196 KB |
Output is correct |
5 |
Correct |
8 ms |
18008 KB |
Output is correct |
6 |
Correct |
8 ms |
18024 KB |
Output is correct |
7 |
Correct |
10 ms |
18008 KB |
Output is correct |
8 |
Correct |
8 ms |
18044 KB |
Output is correct |
9 |
Correct |
9 ms |
18012 KB |
Output is correct |
10 |
Correct |
9 ms |
18036 KB |
Output is correct |
11 |
Correct |
9 ms |
18012 KB |
Output is correct |
12 |
Correct |
9 ms |
18012 KB |
Output is correct |
13 |
Correct |
8 ms |
18012 KB |
Output is correct |
14 |
Correct |
8 ms |
18012 KB |
Output is correct |
15 |
Correct |
9 ms |
18140 KB |
Output is correct |
16 |
Correct |
8 ms |
18008 KB |
Output is correct |
17 |
Correct |
8 ms |
18012 KB |
Output is correct |
18 |
Correct |
8 ms |
18012 KB |
Output is correct |
19 |
Correct |
8 ms |
18012 KB |
Output is correct |
20 |
Correct |
8 ms |
18232 KB |
Output is correct |
21 |
Correct |
8 ms |
18012 KB |
Output is correct |
22 |
Correct |
8 ms |
18068 KB |
Output is correct |
23 |
Correct |
8 ms |
18012 KB |
Output is correct |
24 |
Correct |
8 ms |
18012 KB |
Output is correct |
25 |
Incorrect |
9 ms |
18012 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |