QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#348717#1825. The King's GuardsLaStataleBlueRE 1ms3648kbC++233.8kb2024-03-09 20:41:112024-03-09 20:41:12

Judging History

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

  • [2024-03-09 20:41:12]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3648kb
  • [2024-03-09 20:41:11]
  • 提交

answer

#pragma GCC optimize("O3")
#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>());
    vector<bool> ok(g);
    for(int i=0;i<g;i++){
        int k;
        cin>>k;
        opz[i].resize(k);
        for(auto &j : opz[i]){
            cin>>j;
            j--;
            ok[j]=true;
        }
    }
    
    RollbackUF ds(n);
    auto check = [&]()->bool{
        vector<pair<int,int>> tmp;
        
        vector<set<int>> curr(g);
        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,comp=n;
        for(auto [cost,x,y] : ed){
            if(comp==g)break;
            
            bool flagx=false,flagy=false;
            for(int j=0;j<n;j++){
                if(ok[j] && ds.find(j)==ds.find(x))flagx=true;
                if(ok[j] && ds.find(j)==ds.find(y))flagy=true;
            }
            
            if(!flagx || !flagy){
                if(ds.join(x,y)){
                    ans+=cost;
                    comp--;
                }
                continue;
            }
            
            bool flag = ds.join(x,y);
            if(flag && !check()){
                ds.rollback(ds.time()-2);
            }else if(flag){
                ans+=cost;
                comp--;
            }
        }
        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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3648kb

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: 3616kb

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: 0
Accepted
time: 0ms
memory: 3604kb

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:

526

result:

ok answer is '526'

Test #4:

score: -100
Runtime Error

input:

277 9038 1
226 260 740
44 226 376
151 263 611
67 269 241
120 181 677
259 271 782
37 52 310
48 152 452
168 266 823
85 234 100
46 201 738
129 153 301
69 147 434
13 72 764
13 234 316
171 222 398
214 255 21
112 158 430
20 118 407
45 152 971
205 214 272
221 275 362
198 268 472
117 176 207
31 75 652
139 1...

output:


result: