oj.uz

Submission #652603

# Submission time Handle Problem Language Result Execution time Memory
652603 2022-10-23T13:28:52 Z kym Pastiri (COI20_pastiri) C++14
23 / 100
 1000 ms 181464 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() 
{
	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;
		db2(sh,dd);
		while(node != 1 && (dist[twok[node][0]] == depth[sh] - depth[twok[node][0]]))node=twok[node][0];
		//found the node to place the shepherd
		//now put the shephard here
		int x=sh;
		out.pb(node);
		db(node);
		for(;;) {
			reach
			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;
				i=next(i);
				reach
				s.erase(pi(depth[rev[cur]], rev[cur]));
				
				level[depth[x]].erase(prev(i));
				
			}
			if(x==node)break;
			x=twok[x][0];
			
		}
		FOR(di,1,dist[node]) {
			db(di);
			if(x==1)break;
			x=twok[x][0];
			db(x);
			int nd=depth[x] + dist[node] - di;
			db(nd);

			dbv(level[nd]);
			
			for(auto i=level[nd].lower_bound(st[x]); i!=level[nd].end() && *i <= en[x];i=level[nd].lower_bound(st[x])) {
				reach
				
				if(i==level[nd].end())break;
				int cur=*i;
				i=next(i);
				db2(depth[rev[cur]], rev[cur]);
				s.erase(pi(depth[rev[cur]], rev[cur]));
				level[nd].erase(prev(i));
			}
			reach
		}
	}
	cout << out.size() << '\n';
	for(auto i:out)cout << i << ' ' ;
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 180008 KB Output is correct
2 Execution timed out 1078 ms 181464 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 40660 KB Output is correct
2 Correct 24 ms 40676 KB Output is correct
3 Correct 572 ms 159440 KB Output is correct
4 Correct 578 ms 164264 KB Output is correct
5 Correct 914 ms 155980 KB Output is correct
6 Execution timed out 1034 ms 157856 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 39892 KB Output is correct
2 Correct 34 ms 39904 KB Output is correct
3 Correct 38 ms 40192 KB Output is correct
4 Correct 36 ms 39912 KB Output is correct
5 Correct 39 ms 40124 KB Output is correct
6 Correct 39 ms 40120 KB Output is correct
7 Correct 29 ms 39944 KB Output is correct
8 Correct 23 ms 39924 KB Output is correct
9 Correct 23 ms 40020 KB Output is correct
10 Correct 22 ms 39932 KB Output is correct
11 Correct 25 ms 39892 KB Output is correct
12 Correct 25 ms 39808 KB Output is correct
13 Correct 32 ms 40060 KB Output is correct
14 Correct 26 ms 40052 KB Output is correct
15 Correct 31 ms 40012 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 161088 KB Time limit exceeded
2 Halted 0 ms 0 KB -