QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #591857 | #7181. Graph Cuts | cpismylifeOwO | RE | 9ms | 5964kb | C++20 | 8.1kb | 2024-09-26 18:27:36 | 2024-09-26 18:27:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
const int BlockSize = 317;
struct Edge
{
int u, v, id;
bool isdone;
};
int n, m, q;
vector<int> graph[MaxN];
Edge edge[MaxN];
set<pair<int, int>> s;
void Inp()
{
cin >> n >> m;
for (int x = 1; x <= m; x++)
{
int u, v;
cin >> u >> v;
edge[x].u = u;
edge[x].v = v;
edge[x].id = x;
graph[u].push_back(x);
graph[v].push_back(x);
if (s.find(make_pair(u, v)) != s.end() || s.find(make_pair(v, u)) != s.end())
{
cout << "NIGGA THERE'S MULITEDGE";
exit(0);
}
s.insert(make_pair(u, v));
s.insert(make_pair(v, u));
}
}
bool cur[MaxN];
vector<int> fat;
int fatid[MaxN];
bool cnt[MaxN / BlockSize + 5][2][MaxN];
int mark[MaxN / BlockSize + 5][MaxN];
int fatsum[MaxN / BlockSize + 5][2];
int Blockcnt[MaxN / BlockSize + 5][2][MaxN / BlockSize + 5];
int BlockSum[MaxN / BlockSize + 5];
bool marksmall[MaxN];
void Remove(int k)
{
edge[k].isdone = true;
int u = edge[k].u, v = edge[k].v;
if ((int)graph[u].size() <= BlockSize && (int)graph[v].size() <= BlockSize)
{
BlockSum[k / BlockSize] -= marksmall[k];
marksmall[k] = false;
return;
}
if ((int)graph[u].size() > BlockSize)
{
fatsum[fatid[u]][0] -= cnt[fatid[u]][0][v];
Blockcnt[fatid[u]][0][v / BlockSize] -= cnt[fatid[u]][0][v];
cnt[fatid[u]][0][v] = false;
fatsum[fatid[u]][1] -= cnt[fatid[u]][1][v];
Blockcnt[fatid[u]][1][v / BlockSize] -= cnt[fatid[u]][1][v];
cnt[fatid[u]][1][v] = false;
}
if ((int)graph[v].size() > BlockSize)
{
fatsum[fatid[v]][0] -= cnt[fatid[v]][0][u];
Blockcnt[fatid[v]][0][u / BlockSize] -= cnt[fatid[v]][0][u];
cnt[fatid[v]][0][u] = false;
fatsum[fatid[v]][1] -= cnt[fatid[v]][1][u];
Blockcnt[fatid[v]][1][u / BlockSize] -= cnt[fatid[v]][1][u];
cnt[fatid[v]][1][u] = false;
}
}
int FindFat()
{
for (int x = 0; x < (int)fat.size(); x++)
{
if (fatsum[x][cur[fat[x]] ^ 1] == 0)
{
continue;
}
bool p = cur[fat[x]] ^ 1;
for (int y = 0; y <= n / BlockSize; y++)
{
if (Blockcnt[x][p][y] == 0)
{
continue;
}
for (int z = y * BlockSize; z < min((y + 1) * BlockSize, n + 1); z++)
{
if (cnt[x][p][z])
{
int k = mark[x][z];
Remove(k);
return k;
}
}
}
}
return 0;
}
int FindSmall()
{
for (int x = 0; x <= m / BlockSize; x++)
{
if (BlockSum[x] == 0)
{
continue;
}
for (int y = x * BlockSize; y < min((x + 1) * BlockSize, m + 1); y++)
{
if (marksmall[y])
{
Remove(y);
return y;
}
}
}
return 0;
}
void Exc()
{
for (int x = 1; x <= n; x++)
{
if ((int)graph[x].size() > BlockSize)
{
fatid[x] = (int)fat.size();
fat.push_back(x);
for (int y : graph[x])
{
int v = edge[y].u ^ edge[y].v ^ x;
mark[fatid[x]][v] = y;
cnt[fatid[x]][0][v] = true;
Blockcnt[fatid[x]][0][v / BlockSize]++;
fatsum[fatid[x]][0]++;
}
}
}
cin >> q;
for (int x = 1; x <= q; x++)
{
char p;
cin >> p;
if (p == '+')
{
int i;
cin >> i;
if ((int)graph[i].size() > BlockSize)
{
int k = fatid[i];
for (int x : fat)
{
if (x == i)
{
continue;
}
if (mark[k][x] && !edge[mark[k][x]].isdone)
{
Blockcnt[fatid[x]][0][i / BlockSize]--;
fatsum[fatid[x]][0]--;
cnt[fatid[x]][0][i] ^= 1;
cnt[fatid[x]][1][i] ^= 1;
Blockcnt[fatid[x]][1][i / BlockSize]++;
fatsum[fatid[x]][1]++;
}
}
}
else
{
for (int x : graph[i])
{
if (edge[x].isdone)
{
continue;
}
int v = edge[x].u ^ edge[x].v ^ i;
if ((int)graph[v].size() <= BlockSize)
{
BlockSum[x / BlockSize] -= marksmall[x];
marksmall[x] ^= 1;
BlockSum[x / BlockSize] += marksmall[x];
}
else
{
int k = fatid[v];
Blockcnt[k][0][i / BlockSize]--;
fatsum[k][0]--;
cnt[k][0][i] ^= 1;
cnt[k][1][i] ^= 1;
Blockcnt[k][1][i / BlockSize]++;
fatsum[k][1]++;
}
}
}
cur[i] = true;
}
else if (p == '-')
{
int i;
cin >> i;
if ((int)graph[i].size() > BlockSize)
{
int k = fatid[i];
for (int x : fat)
{
if (x == i)
{
continue;
}
if (mark[k][x] && !edge[mark[k][x]].isdone)
{
Blockcnt[fatid[x]][0][i / BlockSize]++;
fatsum[fatid[x]][0]++;
cnt[fatid[x]][0][i] ^= 1;
cnt[fatid[x]][1][i] ^= 1;
Blockcnt[fatid[x]][1][i / BlockSize]--;
fatsum[fatid[x]][1]--;
}
}
}
else
{
for (int x : graph[i])
{
if (edge[x].isdone)
{
continue;
}
int v = edge[x].u ^ edge[x].v ^ i;
if ((int)graph[v].size() <= BlockSize)
{
BlockSum[x / BlockSize] -= marksmall[x];
marksmall[x] ^= 1;
BlockSum[x / BlockSize] += marksmall[x];
}
else
{
int k = fatid[v];
Blockcnt[k][0][i / BlockSize]++;
fatsum[k][0]++;
cnt[k][0][i] ^= 1;
cnt[k][1][i] ^= 1;
Blockcnt[k][1][i / BlockSize]--;
fatsum[k][1]--;
}
}
}
cur[i] = false;
}
else
{
int p = FindFat();
if (p > 0)
{
cout << p << "\n";
}
else
{
p = FindSmall();
if (p > 0)
{
cout << p << "\n";
}
else
{
cout << 0 << "\n";
}
}
}
}
}
int main()
{
//freopen("C.INP", "r", stdin);
//freopen("C.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5764kb
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: 5764kb
input:
0 0 0
output:
result:
ok q=0
Test #3:
score: 0
Accepted
time: 1ms
memory: 5644kb
input:
0 0 1 ?
output:
0
result:
ok q=1
Test #4:
score: 0
Accepted
time: 9ms
memory: 5964kb
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...