QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#508748	#7181. Graph Cuts	Qingyyx	TL	2408ms	195608kb	C++20	5.2kb	2024-08-07 19:50:13	2024-08-07 19:50:13

Judging History

你现在查看的是最新测评结果

[2024-08-07 19:50:13]
评测

测评结果：TL
用时：2408ms
内存：195608kb

查看

[2024-08-07 19:50:13]
提交

answer

#include <bits/stdc++.h>
#define ll long long
#define enl putchar('\n')
#define all(x) (x).begin(),(x).end()
#define debug(x) printf(" "#x":%d\n",x);
using namespace std;
const int MAXN = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
typedef pair<int, int> pii;
char buf[1 << 21], * p1 = buf, * p2 = buf, obuf[1 << 21], * o = obuf, of[35];
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1)res = res * a % mod; n >>= 1; a = a * a % mod; }return res; }
template <class T = int>inline T read() { T s = 0, f = 1; char c = gc(); for (; !isdigit(c); c = gc())if (c == '-')f = -1; for (; isdigit(c); c = gc())s = s * 10 + c - '0'; return s * f; }
inline void read(int* a, int n) { for (int i = 1; i <= n; ++i)a[i] = read(); }
inline char getc() { char c; for (c = gc(); c == ' ' || c == '\n'; c = gc()); return c; }
inline int inal(char* s) { int n = 0; for (s[0] = gc(); !isalpha(s[0]); s[0] = gc()); for (; isalpha(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline void outd(auto* a, int n) { for (int i = 1; i <= n; ++i)printf("%d ", a[i]); enl; }
int n, m, q;
bitset<MAXN>t[505];
int idg[505][MAXN];
int hav[MAXN], tot, ri[MAXN];
pii g[MAXN];
int deg[MAXN], cnt[MAXN];
const int siz = 400;
bool del[MAXN], inS[MAXN];

struct EG {
    int to, nxt, id;
}e[MAXN << 1];
int head[MAXN], etot;
inline void add(int u, int v, int id) {
    e[etot] = EG {v, head[u], id};
    head[u] = etot++;
}
void clear(int n = MAXN - 1) { memset(head + 1, -1, sizeof(int) * n); etot = 0; }

struct QUE {
    queue<int>q;
    bool inq[MAXN];
    void set(int x) {
        if (inq[x])return;
        q.push(x);
        inq[x] = 1;
    }
    int ask() {
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = 0;
            if (cnt[u] == 1)return u;
        }
        return 0;
    }
}que;



void solve() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int x = read(), y = read();
        g[i] = {x, y};
        deg[x]++, deg[y]++;
    }
    for (int i = 1; i <= n; ++i)
        if (deg[i] >= siz)
            ri[hav[i] = ++tot] = i;

    clear(n);
    for (int i = 1; i <= m; ++i) {
        auto& [u, v] = g[i];
        if (!hav[u] && !hav[v]) {
            add(u, v, i), add(v, u, i);
        } else {
            if (hav[u])idg[hav[u]][v] = i, t[hav[u]].set(v);
            if (hav[v])idg[hav[v]][u] = i, t[hav[v]].set(u);
        }
    }

    del[0] = 1;

    q = read();
    while (q--) {
        char op = getc();
        if (op == '+') {
            int x = read();
            inS[x] = 1;
            for (int i = 1; i <= tot; ++i)
                if (!del[idg[i][x]])
                    t[i].reset(x);
            if (!hav[x]) {
                while (~head[x] && del[e[head[x]].id])
                    head[x] = e[head[x]].nxt;
                for (int i = head[x], pre = i; ~i; pre = i, i = e[i].nxt) {
                    if (del[e[i].id]) {
                        e[pre].nxt = e[i].nxt;
                        continue;
                    }
                    cnt[e[i].id]++;
                    if (cnt[e[i].id] == 1)
                        que.set(e[i].id);
                }
            }
        } else if (op == '-') {
            int x = read();
            inS[x] = 0;
            for (int i = 1; i <= tot; ++i)
                if (!del[idg[i][x]])
                    t[i].set(x);
            if (!hav[x]) {
                while (~head[x] && del[e[head[x]].id])
                    head[x] = e[head[x]].nxt;
                for (int i = head[x], pre = i; ~i; pre = i, i = e[i].nxt) {
                    if (del[e[i].id]) {
                        e[pre].nxt = e[i].nxt;
                        continue;
                    }
                    cnt[e[i].id]--;
                    if (cnt[e[i].id] == 1)
                        que.set(e[i].id);
                }
            }
        } else {
            int ans = que.ask();
            if (!ans) {
                for (int i = 1; i <= tot; ++i) {
                    if (!inS[ri[i]])continue;
                    int pos = t[i]._Find_first();
                    if (pos != t[i].size()) {
                        t[i].reset(pos);
                        if (hav[pos])
                            t[hav[pos]].reset(ri[i]);
                        ans = idg[i][pos];
                        break;
                    }
                }
            }
            del[ans] = 1;
            printf("%d\n", ans);
        }
        // for (int i = 1; i <= tot; ++i)
        //     cout << t[i] << '\n';
        // cout << '\n';
    }
}
signed main(signed argc, char const* argv[]) {
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //=============================================================
    int TxT = 1;
    // TxT = read();
    while (TxT--)
        solve();
    //=============================================================
#ifdef LOCAL
    end :
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 12228kb

input:

output:

result:

ok q=10

Test #2:

score: 0

Accepted

time: 1ms

memory: 10068kb

input:

0 0
0

output:

result:

ok q=0

Test #3:

score: 0

Accepted

time: 0ms

memory: 9944kb

input:

0 0
1
?

output:

result:

ok q=1

Test #4:

score: 0

Accepted

time: 5ms

memory: 12092kb

input:

output:

result:

ok q=100000

Test #5:

score: 0

Accepted

time: 67ms

memory: 194492kb

input:

output:

result:

ok q=100000

Test #6:

score: 0

Accepted

time: 132ms

memory: 195608kb

input:

output:

result:

ok q=100000

Test #7:

score: 0

Accepted

time: 352ms

memory: 194500kb

input:

output:

result:

ok q=100000

Test #8:

score: 0

Accepted

time: 740ms

memory: 194264kb

input:

output:

result:

ok q=100000

Test #9:

score: 0

Accepted

time: 1404ms

memory: 194304kb

input:

output:

result:

ok q=100000

Test #10:

score: 0

Accepted

time: 2408ms

memory: 190540kb

input:

output:

result:

ok q=100000

Test #11:

score: 0

Accepted

time: 45ms

memory: 190360kb

input:

output:

result:

ok q=100000

Test #12:

score: 0

Accepted

time: 72ms

memory: 194664kb

input:

output:

result:

ok q=100000

Test #13:

score: 0

Accepted

time: 126ms

memory: 190756kb

input:

output:

result:

ok q=100000

Test #14:

score: 0

Accepted

time: 360ms

memory: 190580kb

input:

output:

result:

ok q=100000

Test #15:

score: 0

Accepted

time: 767ms

memory: 194332kb

input:

output:

result:

ok q=100000

Test #16:

score: 0

Accepted

time: 1409ms

memory: 193424kb

input:

output:

result:

ok q=100000

Test #17:

score: 0

Accepted

time: 2321ms

memory: 190448kb

input:

output:

result:

ok q=100000

Test #18:

score: -100

Time Limit Exceeded

input:

output: