oj.uz

Submission #833986

# Submission time Handle Problem Language Result Execution time Memory
833986 2023-08-22T09:58:40 Z vjudge1 Pastiri (COI20_pastiri) C++17
49 / 100
 1000 ms 213972 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 500005;
int n,k;
vector<int> V[MAXN];
vector<int> sheeps;
set<int> level[MAXN];
int depth[MAXN];
int twok[MAXN][20];
int st[MAXN], en[MAXN];
int cnt=1;
int rev[MAXN];

void dfs(int x, int p) {
	st[x]=cnt;
	rev[cnt]=x;
	++cnt;
	twok[x][0]=p;
	FOR(i,1,19) {
		if(twok[x][i-1] == -1)continue;
		twok[x][i] = twok[twok[x][i-1]][i-1];
	}
	for(auto v:V[x])if(v!=p) {
		depth[v]=depth[x]+1;
		dfs(v,x);
	}
	en[x]=cnt-1;
}
int dist[MAXN];
set<pi,greater<pi>> s;
vector<int>out;
int32_t main()
{
//    freopen("WHARF.inp"  , "r" , stdin);
//    freopen("WHARF.out" , "w" , stdout);
	IAMSPEED
	cin >> n >> k;
	FOR(i,1,n-1) {
		int a,b; cin >> a >> b;
		V[a].pb(b);
		V[b].pb(a);
	}
	FOR(i,1,k) {
		int x; cin >> x;
		sheeps.pb(x);
	}
	dfs(1,-1);
	for(auto i:sheeps) {
		s.insert(pi(depth[i],i));
	}
	for(auto i:sheeps) {
		level[depth[i]].insert(st[i]);
	}
	queue<int> q;
	FOR(i,0,MAXN-1)dist[i]=oo;
	for(auto i:sheeps){
		q.push(i);
		dist[i]=0;
	}
	while(q.size()) {
		int x=q.front();
		q.pop();
		for(auto v:V[x]){
			if(dist[v] > dist[x]+1) {
				dist[v]=dist[x]+1;
				q.push(v);
			}
		}
	}
	for(auto it=s.begin(); it!=s.end(); it=s.begin()) {
		int sh=it->s;
		int dd=it->f;
		int node=it->s;
		while(node != 1 && (dist[twok[node][0]] == depth[sh] - depth[twok[node][0]]))node=twok[node][0];

		int x=sh;
		out.pb(node);
		db(node);
		for(;;) {

			for(auto i=level[depth[x]].lower_bound(st[node]); i!=level[depth[x]].end() && *i <= en[node];i=level[depth[x]].lower_bound(st[node])) {
				int cur=*i;

				s.erase(pi(depth[rev[cur]], rev[cur]));

				level[depth[x]].erase(i);

			}
			if(x==node)break;
			x=twok[x][0];

		}
		FOR(di,1,dist[node]) {
			if(x==1)break;
			x=twok[x][0];
			int nd=depth[x] + dist[node] - di;

			for(auto i=level[nd].lower_bound(st[x]); i!=level[nd].end() && *i <= en[x];i=level[nd].lower_bound(st[x])) {


				if(i==level[nd].end())break;
				int cur=*i;

				db2(depth[rev[cur]], rev[cur]);
				s.erase(pi(depth[rev[cur]], rev[cur]));
				level[nd].erase(i);
			}

		}
	}
	cout << out.size() << '\n';
	for(auto i:out)cout << i << ' ' ;
}

Compilation message

pastiri.cpp: In function 'int32_t main()':
pastiri.cpp:112:7: warning: unused variable 'dd' [-Wunused-variable]
  112 |   int dd=it->f;
      |       ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 172492 KB Output is correct
2 Correct 272 ms 172504 KB Output is correct
3 Correct 283 ms 172492 KB Output is correct
4 Correct 672 ms 213972 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 40496 KB Output is correct
2 Correct 18 ms 40532 KB Output is correct
3 Correct 589 ms 152748 KB Output is correct
4 Correct 517 ms 157524 KB Output is correct
5 Correct 635 ms 149040 KB Output is correct
6 Correct 844 ms 151172 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39892 KB Output is correct
2 Correct 19 ms 39920 KB Output is correct
3 Correct 18 ms 39960 KB Output is correct
4 Correct 18 ms 39932 KB Output is correct
5 Correct 23 ms 40076 KB Output is correct
6 Correct 23 ms 40008 KB Output is correct
7 Correct 18 ms 39916 KB Output is correct
8 Correct 22 ms 39824 KB Output is correct
9 Correct 17 ms 39940 KB Output is correct
10 Correct 17 ms 39916 KB Output is correct
11 Correct 22 ms 39820 KB Output is correct
12 Correct 20 ms 39820 KB Output is correct
13 Correct 21 ms 39912 KB Output is correct
14 Correct 21 ms 40004 KB Output is correct
15 Correct 21 ms 40044 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 153680 KB Output is correct
2 Correct 580 ms 153468 KB Output is correct
3 Correct 989 ms 178692 KB Output is correct
4 Correct 580 ms 149128 KB Output is correct
5 Execution timed out 1075 ms 153912 KB Time limit exceeded
6 Halted 0 ms 0 KB -