QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #825615 | #9771. Guessing Game | ucup-team296# | WA | 217ms | 22380kb | C++20 | 7.3kb | 2024-12-21 20:52:47 | 2024-12-21 20:52:51 |
Judging History
answer
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct LCA {
vector<int> p;
const int MAX = 20;
vector<vector<int>> jmp;
vector<int> d;
void calcd(int x) {
if (d[x] != 0) return;
if (p[x] == x) return;
calcd(p[x]);
d[x] = d[p[x]] + 1;
}
LCA(vector<int> _p) {
p = _p;
int n = p.size();
for (int i = 0; i< n; i++) {
if (p[i] == -1) p[i] = i;
}
jmp.assign(20, vector<int>(n));
jmp[0] = p;
for (int k = 1; k < MAX; k++) {
for (int i = 0; i < n; i++) {
jmp[k][i] = jmp[k - 1][jmp[k - 1][i]];
}
}
d.resize(n);
for (int i = 0; i < n; i++) {
calcd(i);
}
}
int lca(int x, int y) {
if (d[x] < d[y]) swap(x, y);
for (int k = MAX - 1; k >= 0; k--) {
int xx = jmp[k][x];
if (d[xx] >= d[y]) x = xx;
}
if (x == y) return x;
for (int k = MAX - 1; k >= 0; k--) {
int xx = jmp[k][x];
int yy = jmp[k][y];
if (xx != yy) {
x = xx;
y = yy;
}
}
return p[x];
}
int dist(int x, int y) {
int w = lca(x, y);
return d[x] + d[y] - 2 * d[w];
}
};
struct Dsu {
vector<int> p;
Dsu(int n) {
p.resize(n);
for (int i = 0; i < n; i++) p[i] = i;
}
int get(int x) {
if (p[x] != x) p[x] = get(p[x]);
return p[x];
}
int unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return x;
p[x] = y;
return y;
}
};
int unify(vector<int> &a) {
vector<int> aa = a;
sort(aa.begin(), aa.end());
aa.erase(unique(aa.begin(), aa.end()), aa.end());
for (int i = 0; i < a.size(); i++) {
a[i] = lower_bound(aa.begin(), aa.end(), a[i]) - aa.begin();
}
return aa.size();
}
vector<vector<int>> g;
vector<int> p;
vector<bool> z;
void dfs(int x, int pp) {
z[x] = true;
for (int y : g[x]) {
if (y != pp) {
p[y] = x;
dfs(y, x);
}
}
}
int main() {
ios::sync_with_stdio(false);
int m;
cin >> m;
vector<int> a(m), b(m);
for (int i = 0; i < m; i++) cin >> a[i] >> b[i];
int n1 = unify(a);
int n2 = unify(b);
int n = n1 + n2;
g.resize(n);
Dsu dsu(n);
for (int i = 0; i < m; i++) {
int x = a[i];
int y = n1 + b[i];
int xx = dsu.get(x);
int yy = dsu.get(y);
if (xx != yy) {
g[x].push_back(y);
g[y].push_back(x);
dsu.unite(xx, yy);
}
}
p.assign(n, -1);
z.resize(n);
for (int i = 0; i < n; i++) {
if (!z[i]) dfs(i, -1);
}
LCA lca(p);
vector<int> res(2);
vector<int> bad(n, -1);
vector<pair<int, int>> ends(n);
vector<int> d(n);
vector<bool> bd(n);
Dsu dsu2(n);
Dsu dsu3(n);
for (int i = 0; i < n; i++) {
ends[i] = {i, i};
d[i] = 0;
}
for (int i = 0; i < m; i++) {
int x = a[i];
int y = n1 + b[i];
int xx = dsu2.get(x);
int yy = dsu2.get(y);
if (xx != yy) {
for (int t : {xx, yy}) {
if (bad[t] == -1 && d[t] % 2 == 0) {
int c = (ends[t].first >= n1);
if (d[t] / 2 % 2 == 0) {
res[c]++;
} else {
res[1 - c]++;
}
} else {
res[1 - d[t] / 2 % 2]++;
}
}
int zz = dsu2.unite(xx, yy);
if (bad[xx] != -1 && bad[yy] != -1) {
int a = bad[xx];
int b = bad[yy];
while (true) {
a = dsu3.get(a);
b = dsu3.get(b);
if (a == b) break;
if (lca.d[a] < lca.d[b]) swap(a, b);
int p = lca.p[a];
if (!bd[p]) {
bd[p] = true;
res[p >= n1]--;
}
dsu3.unite(a, p);
}
}
if (bad[xx] != -1) {
bad[zz] = bad[xx];
} else if (bad[yy] != -1) {
bad[zz] = bad[yy];
}
if (bad[zz] == -1) {
int maxd = -1;
pair<int, int> ed;
for (int a : {ends[xx].first, ends[xx].second}) {
for (int b : {ends[yy].first, ends[yy].second}) {
int dd = lca.dist(a, b);
if (dd > maxd) {
maxd = dd;
ed = {a, b};
}
}
}
d[zz] = maxd;
ends[zz] = ed;
if (d[zz] % 2 == 0) {
int c = (ends[zz].first >= n1);
if (d[zz] / 2 % 2 == 0) {
res[c]--;
} else {
res[1 - c]--;
}
} else {
res[1 - d[zz] / 2 % 2]--;
}
}
} else {
if (bad[xx] == -1) {
if (d[xx] % 2 == 0) {
int c = (ends[xx].first >= n1);
if (d[xx] / 2 % 2 == 0) {
res[c]++;
} else {
res[1 - c]++;
}
} else {
res[1 - d[xx] / 2 % 2]++;
}
}
for (int t : {x, y}) {
if (!bd[t]) {
bd[t] = true;
res[t >= n1]--;
}
}
{
int a = x;
int b = y;
while (true) {
a = dsu3.get(a);
b = dsu3.get(b);
if (a == b) break;
if (lca.d[a] < lca.d[b]) swap(a, b);
int p = lca.p[a];
if (!bd[p]) {
bd[p] = true;
res[p >= n1]--;
}
dsu3.unite(a, p);
}
}
if (bad[xx] == -1) {
bad[xx] = x;
} else {
int a = x;
int b = bad[xx];
while (true) {
a = dsu3.get(a);
b = dsu3.get(b);
if (a == b) break;
if (lca.d[a] < lca.d[b]) swap(a, b);
int p = lca.p[a];
if (!bd[p]) {
bd[p] = true;
res[p >= n1]--;
}
dsu3.unite(a, p);
}
}
}
cout << res[0] << " " << res[1] << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3664kb
input:
4 1 1 1 2 2 1 2 2
output:
1 0 0 2 1 2 0 0
result:
ok 8 numbers
Test #2:
score: -100
Wrong Answer
time: 217ms
memory: 22380kb
input:
250000 49324 49323 44443 44445 92513 92513 69591 69591 52085 52082 95024 95025 21004 21005 34373 34371 60771 60772 17131 17134 34885 34882 6011 6015 56103 56105 21055 21054 71592 71593 14894 14895 25774 25771 96225 96224 16444 16442 48432 48432 86954 86952 7202 7202 38661 38665 20063 20063 85383 853...
output:
1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 58 0 59 0 60 0 61 0 62 0...
result:
wrong answer 19251st numbers differ - expected: '8293', found: '8294'