QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#348627#1825. The King's GuardsLaStataleBlueWA 0ms3880kbC++233.2kb2024-03-09 20:05:532024-03-09 20:05:54

Judging History

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

  • [2024-03-09 20:05:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2024-03-09 20:05:53]
  • 提交

answer

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

struct HopcroftKarp { //tested with $n,m\leq 10^5$ (75 ms)
    vector<int> g, l, r; int ans; // 0-based
    HopcroftKarp(int n, int m, const vector<pair<int,int>> &e)
    : g(e.size()), l(n, -1), r(m, -1), ans(0) {
        vector<int> deg(n + 1), a, p, q(n);
        for (auto &[x, y] : e) deg[x]++;
        for (int i = 1; i <= n; i++) deg[i] += deg[i - 1];
        for (auto &[x, y] : e) g[--deg[x]] = y;
        for (bool match=true; match;) {
            a.assign(n,-1), p.assign(n,-1); int t=0; match=false;
            for (int i = 0; i < n; i++)
                if (l[i] == -1) q[t++] = a[i] = p[i] = i;
            for (int i = 0; i < t; i++) {
                int x = q[i];
                if (~l[a[x]]) continue;
                for (int j = deg[x]; j < deg[x + 1]; j++) {
                    int y = g[j];
                    if (r[y] == -1) {
                        while (~y) r[y] = x, swap(l[x], y), x = p[x];
                        match = true; ans++; break;//ans=numero match
                    }
                    if(p[r[y]]==-1)q[t++]=y=r[y],p[y]=x,a[y]=a[x];
                }
            }
        }//nodi sx vengono matchati dando preferenza ai primi(?)
    }//nodi sx numerati da 0 a n-1, nodi dx da 0 a m-1
}; //l[i]= match del nodo sx i (-1 se non è matchato)

struct RollbackUF {
    vector<int> e; vector<pair<int,int>> st;
    RollbackUF(int n) : e(n, -1) {}
    int size(int x) { return -e[find(x)]; }
    int find(int x) { return e[x] < 0 ? x : find(e[x]); }
    int time() { return st.size(); }
    void rollback(int t) {
        for(int i=time();i-->t;) e[st[i].first] = st[i].second;
        st.resize(t);
    }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        st.push_back({a, e[a]}); st.push_back({b, e[b]});
        e[a] += e[b]; e[b] = a; return true;
    }
};

void solve([[maybe_unused]] int t){
    int n,r,g;
    cin>>n>>r>>g;
    
    vector<array<int,3>> ed;
    for(int i=0;i<r;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        ed.push_back({c,a,b});
    }
    sort(ed.begin(),ed.end());
    
    vector opz(g,vector<int>());
    for(int i=0;i<g;i++){
        int k;
        cin>>k;
        opz[i].resize(k);
        for(auto &j : opz[i]){
            cin>>j;
            j--;
        }
    }
    
    RollbackUF ds(n);
    auto check = [&]()->bool{
        vector<pair<int,int>> tmp;
        
        //vector<set<int>> curr(n);
        for(int i=0;i<g;i++){
            for(auto j : opz[i]){
                tmp.emplace_back(i,ds.find(j));
            }
        }
        
        return HopcroftKarp(g,n,tmp).ans==g;
    };
    
    if(!check()){
        cout<<"-1\n";
    }else{
        int ans=0;
        for(auto [cost,x,y] : ed){
            if(ds.join(x,y) && !check()){
                ds.rollback(ds.time()-1);
            }else{
                ans+=cost;
            }
        }
        cout<<ans<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3660kb

input:

5 6 2
1 2 1
1 3 4
2 4 2
2 5 5
3 4 7
4 5 3
2 1 2
2 2 4

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 19 6
1 5 761
6 8 606
3 9 648
2 4 115
5 8 814
1 2 712
4 10 13
5 10 797
3 4 956
1 7 73
5 7 192
2 7 110
5 9 302
3 6 120
6 9 494
1 3 668
3 7 966
6 10 974
3 8 41
2 10 5
3 6 4 3
2 1 7
2 10 8
3 10 7 8
2 2 1

output:

429

result:

ok answer is '429'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3880kb

input:

10 43 3
1 3 656
2 6 856
4 10 99
5 6 900
2 7 766
4 7 582
2 8 135
5 7 831
3 5 12
3 10 789
1 8 66
4 9 390
1 7 238
6 7 960
1 4 624
3 9 602
7 10 366
5 8 526
2 9 561
6 10 722
2 5 904
3 4 35
1 9 768
5 9 457
6 8 61
4 6 192
4 5 96
5 10 747
8 9 611
7 8 953
3 8 449
2 4 228
1 6 197
9 10 160
3 6 869
1 2 785
4 8 ...

output:

6972

result:

wrong answer expected '526', found '6972'