# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
120231 |
2019-06-24T03:27:45 Z |
TuGSGeReL |
Game (IOI14_game) |
C++14 |
|
2 ms |
384 KB |
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
int par[1501], sz[1501], rsz[1501], nn, rsz1[1501][1501];
int fnd(int x) {
if ( par[x] != x )
return par[x] = fnd(par[x]);
return par[x];
}
void dsu(int u, int v) {
int pru = fnd(u), prv = fnd(v);
par[pru] = prv;
sz[prv] += sz[pru];
rsz[prv] = rsz[pru] + rsz[prv] - rsz1[pru][prv] - rsz1[prv][pru];
}
void rdsu(int u, int v) {
int pru = fnd(u), prv = fnd(v);
rsz1[pru][prv]++;
rsz1[prv][pru]++;
rsz[pru]++;
rsz[prv]++;
}
bool tusdaa(int u, int v) {
int pru = fnd(u), prv = fnd(v);
if ( pru == prv )
return 1;
if ( rsz[prv] + 1 == (nn - sz[prv]) * sz[prv] )
return 1;
if ( rsz[pru] + 1 == (nn - sz[pru]) * sz[pru] )
return 1;
return 0;
}
void initialize(int n) {
nn = n;
for (int i = 0; i < n; i++)
par[i]= i, sz[i] = 1;
}
int hasEdge(int u, int v) {
if ( !tusdaa(u, v) ) {
rdsu(u, v);
return 0;
} else {
dsu(u, v);
return 1;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |