QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#348627 | #1825. The King's Guards | LaStataleBlue | WA | 0ms | 3880kb | C++23 | 3.2kb | 2024-03-09 20:05:53 | 2024-03-09 20:05:54 |
Judging History
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'