Submission #1270363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270363		HiepVu217	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	22 ms	6212 KiB

cleaning

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;

const int N = 1e5 + 10;
int n, q, deg[N], cnt = 0, dis[N], used[N], ans, res, dem[N], up[N][20], logn;
vector<int>adj[N];

void dfs(int u, int p){
	 for(auto v : adj[u]){
		 if(v == p) continue;
		 dis[v] = dis[u] + 1;
		 dem[dis[v]]++;
		 dfs(v, u);
	 }
}

int lca(int u, int v){
	if(dis[u] < dis[v]){
	   swap(u, v);
	}
	for(int j = logn;j >= 1;j--){
		if(dis[up[u][j]] >= dis[v]){
		   u = up[u][j];
		}
	}
	if(u == v) return u;
	for(int j = logn;j >= 1;j--){
		if(up[u][j] != up[v][j]){
		   u = up[u][j];
		   v = up[v][j];
		}
	}
	return up[u][0];
}

void sub1(){
	 dis[1] = 0;
	 dfs(1, 1);
	 for(int i = 1;i <= n;i++){
		 if(deg[i] == 1){
			cnt++;
			dem[dis[i]];
		 }
	 }
	 int max_d = 0;
	 for(int i = n;i >= 1;i--){
		 if(dem[i] != 0){
			max_d = i;
			break;
		 }
	 }
	 int l = 0, r = max_d;
	 int kq = 0;
	 while(l <= r){
		   if(dem[l] > 0 && dem[r] > 0){
			  kq += dis[r] + dis[l];
			  dem[l]--;
			  dem[r]--;
		   }
		   else{
			  if(dem[l] <= 0){
				 l++;
				 continue;
			  }
			  else{
				 r--;
				 continue;
			  }
		   }
	 }
	 cout << r << "\n";
	 while(q--){
		   int d;
		   cin >> d;
	 }
}

void sub2(){
	 while(q--){
		   int d;
		   cin >> d;
		   for(int j = 1;j <= d;j++){
			   int u;
			   cin >> u;
		   }
		   if((n - 1) % 2 != 0){
		   	  cout << "-1\n";
		   	  continue;
		   }
		   else{
			  cout << (n - 1) + d << "\n";
		   }
	 }
}

int main(){
	if(fopen("crt.inp", "r")){
	   freopen("crt.inp", "r", stdin);
	   freopen("crt.out", "w", stdout);
	}
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i < n;i++){
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	if(q == 1){
	   sub2();
	}
	else{
	   if(n <= 20000 && q <= 300){
		  sub1();
	   }
	}
	return 0;
}

Compilation message (stderr)

cleaning.cpp: In function 'int main()':
cleaning.cpp:102:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |            freopen("crt.inp", "r", stdin);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:103:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |            freopen("crt.out", "w", stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30