Wannafly Winter Camp 2020-Day3

赛时爆零了 记的是补题qwq

3A. 黑色气球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
int a[1005][1005],h[1005];
int main(){
int n; sc(n); ll sum(0); rep(i,0,n) rep(j,0,n)
sc(a[i][j]),sum+=1ll*a[i][j],h[i]+=a[i][j];
if(n==2) return pf("1 1\n"),0;
sum/=(2ll*n-2); rep(i,0,n) pf("%d ",(-1*sum+h[i])/(n-2));
}

3C. 无向图定向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int n,m,ans,c[20];
vector<int>vv[20];
int judge(int x,int id){
for(int t:vv[x]) if(c[t]==id) return 1;
return 0;
}
void dfs(int x,int num){
if(ans<=num) return;
if(x>n) return ans=min(ans,num),(void)0;
rep(i,1,num+1) if(!judge(x,i)){
c[x]=i; dfs(x+1,num); c[x]=0;
} c[x]=num+1; dfs(x+1,num+1); c[x]=0;
}
int main(){
sc(n); sc(m); ans=1e9; while(m--){
int u,v; sc(u); sc(v);
vv[u].push_back(v); vv[v].push_back(u);
} dfs(1,0); printf("%d\n",ans-1);
}

3E. 棋技哥

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
char s[505],c;
int main(){
int _; sc(_); while(_--){
int n,m; sc(n); sc(m); scs(s); c=s[0];
rep(i,1,n) scs(s); puts(c=='0'?"aoligei":"call");
}
}

3G. 火山哥周游世界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 5e5 + 5;
int n,k,vis[maxn];
ll num[maxn],sum[maxn];
ll mx1[maxn],mx2[maxn];
vector<pii>vv[maxn];
void upd(int id,ll x){
if(x>=mx1[id]) mx2[id]=mx1[id],mx1[id]=x;
else if(x>mx2[id]) mx2[id]=x;
}
void dfs1(int x,int f){
if(vis[x]) num[x]++;
sum[x]=mx1[x]=mx2[x]=0;
for(pii t:vv[x]){
ll y=t.first,z=t.second;
if(y==f) continue; dfs1(y,x);
num[x]+=num[y];
sum[x]+=sum[y]+(num[y]>0)*z;
upd(x,mx1[y]+(num[y]>0)*z);
}
}
void dfs2(int x,int f){
for(pii t:vv[x]){
ll y=t.first,z=t.second;
if(y==f) continue;
sum[y]=sum[x]-z*(num[y]>0)+z*(n-num[y]>0);
if(num[y]!=n&&mx1[y]+z==mx1[x]) upd(y,mx2[x]+z);
else if(num[y]!=n) upd(y,mx1[x]+z); dfs2(y,x);
}
}
int main(){
sc(n); sc(k); rep(i,1,n){
ll u,v,w; scl(u); scl(v); scl(w);
vv[u].push_back(make_pair(v,w));
vv[v].push_back(make_pair(u,w));
} int a0; sc(a0); vis[a0]++; k--;
while(k--){ int a; sc(a); vis[a]++; }
dfs1(a0,0); dfs2(a0,0);
rep(i,1,n+1) pf("%lld\n",sum[i]*2-mx1[i]);
}