QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#380677	#7181. Graph Cuts	ucup-team992^#	TL	3436ms	27724kb	C++20	3.2kb	2024-04-07 08:31:41	2024-04-07 08:31:41

Judging History

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

[2024-04-07 08:31:41]
评测

测评结果：TL
用时：3436ms
内存：27724kb

查看

[2024-04-07 08:31:41]
提交

answer

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ar array
typedef int uci;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void solve(){
    int n, m;
    cin >> n >> m;

    vector<int> deg(n);
    vector<int> lbig;
    vector<int> big(n, -1);
    vector<int> state(n);
    vector<vector<bitset<100000>>> sides(2);
    vector<unordered_map<int, int>> adj(n);
    vector<ar<int, 2>> edges;
    edges.push_back({});
    for(int i{}; i < m; ++i){
        int u, v;
        cin >> u >> v;
        u--, v--;

        edges.push_back({u, v});
        adj[u][v] = i+1;
        adj[v][u] = i+1;
        deg[u]++, deg[v]++;
    }

    int sq = sqrt(n);
    for(int i{}; i < n; ++i){
        if(deg[i] >= sq){
            big[i] = sides[0].size();
            lbig.push_back(i);
            sides[0].push_back({});
            for(auto t : adj[i]){
                sides[0].back().set(t.F);
            }
            sides[1].push_back({});
        }
    }

    int q;
    cin >> q;

    vector<unordered_map<int, int>> bigadj(n);
    for(int i : lbig){
        vector<int> te;
        for(auto &t : adj[i]){
            bigadj[t.F][i] = t.S;
            bigadj[i][t.F] = t.S;
            te.push_back(t.F);
        }
        for(auto &t : te){
            adj[t].erase(i);
            adj[i].erase(t);
        }
    }


    bitset<100001> gv{};
    for(int i{}; i < q; ++i){
        char c;
        cin >> c;
        if(c == '+' || c == '-'){
            int v;
            cin >> v;
            v--;

            state[v] = 1-state[v];
            for(auto &t : bigadj[v]){
                sides[1-state[v]][big[t.F]].flip(v);
                sides[state[v]][big[t.F]].flip(v);
            }
            for(auto [i, c] : adj[v]){
                if(state[i] != state[v]){
                    gv.set(c);
                }else{
                    gv.reset(c);
                }
            }
        }else{
            int lsb = gv._Find_first();
            if(lsb != 100001){
                gv.reset(lsb);
                cout << lsb << '\n';
                adj[edges[lsb][0]].erase(edges[lsb][1]);
                adj[edges[lsb][1]].erase(edges[lsb][0]);
            }else{
                bool found = false;
                for(auto &t : lbig){
                    int st = 1-state[t];
                    int ind = big[t];
                    auto a = sides[st][ind]._Find_first();
                    if(a != 100000){
                        sides[st][ind].reset(a);
                        if(big[a] != -1){
                            sides[state[t]][big[a]].reset(t);
                        }

                        cout << bigadj[t][a] << '\n';
                        found = true;
                        bigadj[a].erase(t);
                        bigadj[t].erase(a);
                        break;
                    }
                }
                if(!found){
                    cout << 0 << '\n';
                }
            }
        }
    }
}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve();
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3680kb

input:

output:

result:

ok q=10

Test #2:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

0 0
0

output:

result:

ok q=0

Test #3:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

0 0
1
?

output:

result:

ok q=1

Test #4:

score: 0

Accepted

time: 21ms

memory: 4088kb

input:

output:

result:

ok q=100000

Test #5:

score: 0

Accepted

time: 804ms

memory: 27588kb

input:

output:

result:

ok q=100000

Test #6:

score: 0

Accepted

time: 807ms

memory: 27724kb

input:

output:

result:

ok q=100000

Test #7:

score: 0

Accepted

time: 1113ms

memory: 27068kb

input:

output:

result:

ok q=100000

Test #8:

score: 0

Accepted

time: 1935ms

memory: 27476kb

input:

output:

result:

ok q=100000

Test #9:

score: 0

Accepted

time: 3436ms

memory: 27692kb

input:

output:

result:

ok q=100000

Test #10:

score: -100

Time Limit Exceeded

input:

output: