Submission #1139505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139505		Math4Life2020	Meetings 2 (JOI21_meetings2)	C++20	4 / 100	4098 ms	129612 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 2e5+5; const ll INF = 1e18;
vector<ll> adj[Nm];

int main() {
	ll N; cin >> N;
	for (ll i=0;i<(N-1);i++) {
		ll a,b; cin >> a >> b; a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	ll dist[N][N];
	for (ll x=0;x<N;x++) {
		queue<array<ll,3>> q0;
		q0.push({x,0,-1});
		while (!q0.empty()) {
			auto A0 = q0.front(); q0.pop();
			ll y = A0[0]; ll t = A0[1]; ll py = A0[2];
			dist[x][y]=t;
			for (ll z: adj[y]) {
				if (z != py) {
					q0.push({z,t+1,y});
				}
			}
		}
	}
	vector<ll> ansf2(N+1,1);
	for (ll B=1;B<(1<<N);B++) {
		ll cval = INF; ll ncnt = 0;
		vector<ll> velem;
		for (ll x=0;x<N;x++) {
			if ((B>>x)&1) {
				velem.push_back(x);
			}
		}
		for (ll x=0;x<N;x++) {
			ll cqry = 0;
			for (ll y: velem) {
				cqry += dist[x][y];
			}
			if (cqry==cval) {
				ncnt++;
			} else if (cqry<cval) {
				cval = cqry;
				ncnt = 1;
			}
		}
		ansf2[velem.size()]=max(ansf2[velem.size()],ncnt);
	}
	for (ll i=1;i<=N;i++) {
		cout << ansf2[i] <<"\n";
	}
}

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