oj.uz

Submission #652604

# Submission time Handle Problem Language Result Execution time Memory
652604 2022-10-23T13:30:25 Z kym Pastiri (COI20_pastiri) C++14
49 / 100
 1000 ms 222644 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(;;) {
			
			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);
				
				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;
			
			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;
				i=next(i);
				db2(depth[rev[cur]], rev[cur]);
				s.erase(pi(depth[rev[cur]], rev[cur]));
				level[nd].erase(prev(i));
			}
			
		}
	}
	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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 172784 KB Output is correct
2 Correct 348 ms 173004 KB Output is correct
3 Correct 357 ms 179192 KB Output is correct
4 Correct 825 ms 222644 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 40568 KB Output is correct
2 Correct 26 ms 40628 KB Output is correct
3 Correct 607 ms 153200 KB Output is correct
4 Correct 612 ms 157944 KB Output is correct
5 Correct 775 ms 149428 KB Output is correct
6 Correct 870 ms 151560 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 40004 KB Output is correct
2 Correct 22 ms 39920 KB Output is correct
3 Correct 23 ms 39972 KB Output is correct
4 Correct 29 ms 39884 KB Output is correct
5 Correct 21 ms 40020 KB Output is correct
6 Correct 22 ms 40084 KB Output is correct
7 Correct 21 ms 39904 KB Output is correct
8 Correct 22 ms 39956 KB Output is correct
9 Correct 24 ms 40012 KB Output is correct
10 Correct 25 ms 39996 KB Output is correct
11 Correct 24 ms 39884 KB Output is correct
12 Correct 21 ms 39764 KB Output is correct
13 Correct 22 ms 40048 KB Output is correct
14 Correct 22 ms 40032 KB Output is correct
15 Correct 22 ms 40056 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 153828 KB Output is correct
2 Correct 729 ms 160260 KB Output is correct
3 Execution timed out 1091 ms 186024 KB Time limit exceeded
4 Halted 0 ms 0 KB -