Wannafly Winter Camp 2020-Day3

#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));
}

#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);
}

#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");
    }
}

#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]);
}