比赛 |
2025暑期集训第4场 |
评测结果 |
T |
题目名称 |
战略游戏 |
最终得分 |
0 |
用户昵称 |
二乾五 |
运行时间 |
1.563 s |
代码语言 |
C++ |
内存使用 |
5.93 MiB |
提交时间 |
2025-07-05 11:37:46 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)
ll n,sz[1505];
bool ok[1505][1505];
vector<vector<ll>>a(1505);
priority_queue<pair<ll,ll>>bucket;
int main(){
#ifndef ONLINE_JUDGE
freopen("strategic.in" ,"r",stdin );
freopen("strategic.out","w",stdout);
#endif
while(cin>>n){
foru(i,1,n-1)foru(j,i+1,n)ok[i][j]=ok[j][i]=0;
while(!bucket.empty())bucket.pop();
foru(i,0,n-1){sz[i]=0;a[i].clear();}
foru(i,1,n){
ll x,tmp;
// char c;
// cin>>x;
// cin>>c;cin>>c;
// cin>>tmp;
// cin>>c;
scanf("%lld:(%lld)",&x,&tmp);
foru(j,1,tmp){
ll t;
cin>>t;
a[x].push_back(t);
a[t].push_back(x);
sz[t]++;
}
sz[x]+=tmp;
bucket.push({sz[x],x});
}
ll cnt=0,ans=0;
while(cnt<n-1){
ll u=bucket.top().second;
bucket.pop();
bool used=0;
for(auto v:a[u]){
if(!ok[u][v]){
cnt++;
ok[u][v];
used=1;
}
}
ans+=used;
}
cout<<ans<<endl;
// //-
// foru(i,0,n-1){
// for(auto v:a[i]){
// cerr<<v<<" ";
// }
// cerr<<endl;
// // cerr<<sz[i]<<endl;
// }
// //-
}
return 0;
}