QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#348717 | #1825. The King's Guards | LaStataleBlue | RE | 1ms | 3648kb | C++23 | 3.8kb | 2024-03-09 20:41:11 | 2024-03-09 20:41:12 |
Judging History
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...