Submission #893419

#	Time	Username	Problem	Language	Result	Execution time	Memory
893419		vjudge1	Meetings 2 (JOI21_meetings2)	C++17	4 / 100	23 ms	604 KiB

meetings2

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1005;
vector <int> g[N];
int d[N][N];
int ans[N];
signed main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    queue <int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        d[i][i]=0;
        while(!q.empty()){
            int v=q.front();
            q.pop();
            for(auto to : g[v]){
                if(d[i][to]==0 && to!=i){
                    d[i][to]=d[i][v]+1;
                    q.push(to);
                }
            }
        }
    }
    
    for(int i=0;i<(1<<n);i++){
        vector <int> v;
        for(int j=0;j<n;j++){
            if((i & (1<<j))!=0){
                v.pb(j);
            }
        }
        int mn=1e9,cnt=0;
        for(int i=1;i<=n;i++){
            int sum=0;
            for(auto x : v){
                sum+=d[i][x+1];
            }
            if(sum<mn){
                mn=sum;
                cnt=1;
            }
            else if(sum==mn)cnt++;
        }
        ans[v.size()]=max(ans[v.size()],cnt);
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<"\n";
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80