QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #592361 | #7181. Graph Cuts | rtgsp | RE | 9ms | 9992kb | C++20 | 5.7kb | 2024-09-26 22:03:53 | 2024-09-26 22:03:57 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e5 + 2, blocksize = 320, mod = 1e9 + 7;
int n, m, q, B[maxn], u[maxn], v[maxn], id[maxn], cnt = 0, x, sum[maxn], sumheavy[2][320][maxn], tot, totheavy[2][320], res;
bool in[maxn], ok[maxn], okheavy[2][320][maxn], off[maxn];
char t;
vector<int> heavy, adj[maxn], heavyadj[maxn];
int main()
{
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++)
B[i] = (i - 1)/blocksize + 1;
for (int i = 1; i <= m; i++)
{
cin >> u[i] >> v[i];
adj[u[i]].push_back(i);
adj[v[i]].push_back(i);
}
for (int i = 1; i <= n; i++)
{
if (adj[i].size() > blocksize)
{
cnt++;
heavy.push_back(i);
id[i] = cnt;
for (int j : adj[i])
{
okheavy[1][cnt][j] ^= 1;
totheavy[1][cnt] += okheavy[1][cnt][j] - (okheavy[1][cnt][j] ^ 1);
sumheavy[1][cnt][B[j]] += okheavy[1][cnt][j] - (okheavy[1][cnt][j] ^ 1);
if (adj[u[j] ^ v[j] ^ i].size() > blocksize) heavyadj[i].push_back(j);
}
}
}
cin >> q;
while (q--)
{
cin >> t;
if (t != '?')
{
cin >> x;
in[x] ^= 1;
if (adj[x].size() <= blocksize)
{
for (int i : adj[x])
{
int y = u[i] ^ v[i] ^ x;
if (adj[y].size() <= blocksize)
{
if (!off[i])
{
ok[i] ^= 1;
tot += ok[i] - (ok[i] ^ 1);
sum[B[i]] += ok[i] - (ok[i] ^ 1);
}
}
else
{
if (!off[i])
{
cnt = id[x];
okheavy[0][cnt][i] ^= 1;
totheavy[0][cnt] += okheavy[0][cnt][i] - (okheavy[0][cnt][i] ^ 1);
sumheavy[0][cnt][B[i]] += okheavy[0][cnt][i] - (okheavy[0][cnt][i] ^ 1);
okheavy[1][cnt][i] ^= 1;
totheavy[1][cnt] += okheavy[1][cnt][i] - (okheavy[1][cnt][i] ^ 1);
sumheavy[1][cnt][B[i]] += okheavy[1][cnt][i] - (okheavy[1][cnt][i] ^ 1);
}
}
}
}
else
{
for (int i : heavyadj[x])
{
if (!off[i])
{
int y = u[i] ^ v[i] ^ x;
cnt = id[y];
okheavy[0][cnt][i] ^= 1;
totheavy[0][cnt] += okheavy[0][cnt][i] - (okheavy[0][cnt][i] ^ 1);
sumheavy[0][cnt][B[i]] += okheavy[0][cnt][i] - (okheavy[0][cnt][i] ^ 1);
okheavy[1][cnt][i] ^= 1;
totheavy[1][cnt] += okheavy[1][cnt][i] - (okheavy[1][cnt][i] ^ 1);
sumheavy[1][cnt][B[i]] += okheavy[1][cnt][i] - (okheavy[1][cnt][i] ^ 1);
}
}
}
}
else
{
res = 0;
for (int i = 1; i <= B[m]; i++)
{
if (res != 0 || sum[i] == 0) continue;
for (int j = (i - 1)*blocksize + 1; j <= min(m, i*blocksize); j++)
{
if (ok[j])
{
res = j;
break;
}
}
}
if (res != 0)
{
off[res] = true;
ok[res] ^= 1;
tot += ok[res] - (ok[res] ^ 1);
sum[B[res]] += ok[res] - (ok[res] ^ 1);
cout << res << '\n';
continue;
}
for (int x : heavy)
{
if (res != 0 || totheavy[in[x]][id[x]] == 0) continue;
for (int i = 1; i <= B[m]; i++)
{
if (res != 0 || sumheavy[in[x]][id[x]][i] == 0) continue;
for (int j = (i - 1)*blocksize + 1; j <= min(m, i*blocksize); j++)
if (okheavy[in[x]][id[x]][j])
{
res = j;
break;
}
if (res != 0)
{
off[res] = true;
okheavy[in[x]][id[x]][res] ^= 1;
totheavy[in[x]][id[x]] += okheavy[in[x]][id[x]][res] - (okheavy[in[x]][id[x]][res] ^ 1);
sumheavy[in[x]][id[x]][B[res]] += okheavy[in[x]][id[x]][res] - (okheavy[in[x]][id[x]][res] ^ 1);
int y = u[res] ^ v[res] ^ x;
if (adj[y].size() > blocksize)
{
okheavy[in[y]][id[y]][res] ^= 1;
totheavy[in[y]][id[y]] += okheavy[in[y]][id[y]][res] - (okheavy[in[y]][id[y]][res] ^ 1);
sumheavy[in[y]][id[y]][B[res]] += okheavy[in[y]][id[y]][res] - (okheavy[in[y]][id[y]][res] ^ 1);
}
break;
}
}
}
cout << res << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9820kb
input:
4 5 1 2 1 3 1 4 2 3 2 4 10 + 1 + 2 ? ? ? ? ? - 2 ? ?
output:
2 3 4 5 0 1 0
result:
ok q=10
Test #2:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
0 0 0
output:
result:
ok q=0
Test #3:
score: 0
Accepted
time: 1ms
memory: 7772kb
input:
0 0 1 ?
output:
0
result:
ok q=1
Test #4:
score: 0
Accepted
time: 9ms
memory: 9992kb
input:
1000 2000 1 50 1 88 331 1 1 352 1 497 2 32 2 282 550 2 989 2 334 3 3 665 4 38 4 69 4 343 4 451 589 4 917 4 89 5 5 162 675 5 681 6 7 22 127 7 7 592 7 672 787 7 8 310 107 9 9 137 184 9 9 244 378 9 446 9 9 658 883 9 65 10 75 10 414 10 10 468 686 10 245 11 269 11 11 386 403 11 493 11 394 12 493 12 565 1...
output:
1 4 5 8 9 10 12 14 16 18 19 25 27 29 33 38 39 40 42 47 48 49 50 56 58 59 62 63 67 69 70 71 73 75 79 81 82 83 84 87 89 91 94 97 101 103 104 106 107 108 109 110 113 114 115 118 120 121 122 125 126 129 130 131 132 133 134 135 137 145 147 148 34 149 152 153 154 155 156 157 159 160 163 167 171 105 173 17...
result:
ok q=100000
Test #5:
score: -100
Runtime Error
input:
447 99681 2 1 1 3 4 1 1 5 1 6 1 7 1 8 9 1 10 1 1 11 1 12 1 13 1 14 1 15 1 16 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 1 26 27 1 28 1 1 29 30 1 31 1 1 32 33 1 1 34 1 35 36 1 37 1 38 1 39 1 40 1 1 41 1 42 43 1 44 1 45 1 46 1 1 47 48 1 49 1 1 50 1 51 1 52 53 1 54 1 55 1 1 56 57 1 1 58 59 1 60 1 1 6...