QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #318993 | #7181. Graph Cuts | PhanDinhKhoi# | TL | 9ms | 17868kb | C++17 | 4.6kb | 2024-02-01 13:57:15 | 2024-02-01 13:57:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef pair<ld,ld> pld;
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int) (x).size())
const int sq = 370;
int del[100005];
int deg[100005];
int inset[100005];
int isbig[100005];
vector<int> vadj[100005];
vector<int> bigadj[100005];
int cnt[100005];
int eu[100005];
int ev[100005];
int bb[100005];
int type[100005];
set<int> big;
set<int> small;
set<int> mid0[100005];
set<int> mid1[100005];
void upd(int e, int i){
if (i == 1) {
if (type[e] == 1) {
if (cnt[e] == 1) {
small.erase(e);
}
cnt[e]++;
if (cnt[e] == 1) {
small.insert(e);
}
}
else if (type[e] == 2) {
mid0[bb[e]].erase(e);
mid1[bb[e]].insert(e);
}
else if (type[e] == 3) {
if (cnt[e] == 1) {
big.erase(e);
}
cnt[e]++;
if (cnt[e] == 1) {
big.insert(e);
}
}
}
else {
if (type[e] == 1) {
if (cnt[e] == 1) {
small.erase(e);
}
cnt[e]--;
if (cnt[e] == 1) {
small.insert(e);
}
}
else if (type[e] == 2) {
mid1[bb[e]].erase(e);
mid0[bb[e]].insert(e);
}
else if (type[e] == 3) {
if (cnt[e] == 1) {
big.erase(e);
}
cnt[e]--;
if (cnt[e] == 1) {
big.insert(e);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n , m ;
cin >> n >> m ;
for (int i = 1 ; i <= m ; i++) {
int u , v; cin >> u >> v;
deg[u]++;
deg[v]++;
vadj[u].pb(i);
vadj[v].pb(i);
eu[i] = u;
ev[i] = v;
}
vector<int> vbig;
for (int i = 1 ; i <= n ; i++) {
if (deg[i] >= sq) {isbig[i] = 1;vbig.pb(i);}
}
int m1 = 0;
for (int i = 1 ; i <= m ; i++) {
if (isbig[eu[i]] && isbig[ev[i]]) {
type[i] = 3;
bigadj[eu[i]].pb(i);
bigadj[ev[i]].pb(i);
}
else if (!isbig[eu[i]] && !isbig[ev[i]]) {
type[i] = 1;
}
else {
type[i] = 2;
if (isbig[eu[i]]) bb[i] = eu[i]; else bb[i] = ev[i];
mid0[bb[i]].insert(i);
}
}
for (int i = 1 ; i <= n ; i++) {
m1 = max(m1,sz(vadj[i]));
m1 = max(m1,sz(bigadj[i]));
}
m1 = max(m1,sz(vbig));
assert(m1 < 505);
int q ; cin >> q;
while (q--) {
char t ; cin >> t;
if (t == '+') {
int id; cin >> id;
if (!isbig[id]) {
for (auto e : vadj[id]) {
if (del[e]) continue;
upd(e,1);
}
}
else {
for (auto e : bigadj[id]) {
if (del[e]) continue;
upd(e,1);
}
}
inset[id] = 1;
}
else if (t == '-') {
int id; cin >> id;
if (!isbig[id]) {
for (auto e : vadj[id]) {
if (del[e]) continue;
upd(e,0);
}
}
else {
for (auto e : bigadj[id]) {
if (del[e]) continue;
upd(e,0);
}
}
inset[id] = 0;
}
else {
int ans = 0;
if (!small.empty()) {
auto it = small.begin();
ans = (*it);small.erase(it);
del[ans] = 1;
}
else if (!big.empty()) {
auto it = big.begin();
ans = (*it);big.erase(it);
del[ans] = 1;
}
else {
for (auto id : vbig) {
if (ans != 0) break;
if (inset[id]) {
if (!mid0[id].empty()) {
auto it = mid0[id].begin();
ans = (*it);mid0[id].erase(it);
del[ans] = 1;
break;
}
}
else {
if (!mid1[id].empty()) {
auto it = mid1[id].begin();
ans = (*it);mid1[id].erase(it);
del[ans] = 1;
break;
}
}
}
}
cout << ans << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 17708kb
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: 0ms
memory: 17868kb
input:
0 0 0
output:
result:
ok q=0
Test #3:
score: 0
Accepted
time: 3ms
memory: 17812kb
input:
0 0 1 ?
output:
0
result:
ok q=1
Test #4:
score: 0
Accepted
time: 9ms
memory: 17812kb
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
Time Limit Exceeded
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...