oj.uz

Submission #945059

# Submission time Handle Problem Language Result Execution time Memory
945059 2024-03-13T11:05:04 Z pcc Meetings (JOI19_meetings) C++17
7 / 100
 597 ms 262144 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

/*
  int x = Query(0, 1, 2);
    Bridge(u, u + 1);
*/

const int mxn = 2020;
set<int> tree[mxn];
int sz[mxn];
vector<int> perm;
bitset<mxn> done;
bitset<mxn> del;
int N;

int ask(int a,int b,int c){
	//assert(a != b&&b!=c&&c != a);
	return Query(a,b,c);
}
void add_edge(int a,int b){
	//assert(a != b);
	tree[a].insert(b);
	tree[b].insert(a);
	cerr<<"ADD:"<<a<<' '<<b<<endl;
}

void del_edge(int a,int b){
	cerr<<"DEL:"<<a<<' '<<b<<endl;
	assert(tree[a].find(b) != tree[a].end());
	tree[a].erase(b);
	tree[b].erase(a);
}

void szdfs(int now,int par){
	sz[now] = 1;
	for(auto nx:tree[now]){
		if(del[nx]||nx==par)continue;
		szdfs(nx,now);
		sz[now] += sz[nx];
	}
	return;
}

int get_centroid(int now,int par,int tar){
	for(auto nxt:tree[now]){
		if(nxt == par||del[nxt])continue;
		if(sz[nxt]>tar)return get_centroid(nxt,now,tar);
	}
	return now;
}

void calc(int now,int tar){
	szdfs(now,now);
	cerr<<"CALC:"<<now<<' '<<tar<<' '<<sz[now]<<endl;
	if(sz[now] == 1){
		add_edge(now,tar);
		return;
	}
	else if(sz[now] == 2){
		int nx;
		for(auto &i:tree[now])if(!del[i])nx = i;
		int r = ask(now,nx,tar);
		if(r == tar){
			del_edge(now,nx);
			add_edge(tar,now);
			add_edge(tar,nx);
		}
		else if(r == nx||r == now){
			add_edge(r,tar);
		}
		else{
			done[r] = true;
			del_edge(now,nx);
			add_edge(now,r);
			add_edge(r,nx);
			add_edge(r,tar);
		}
		return;
	}
	now = get_centroid(now,now,(sz[now]-1)/2);
	vector<int> ch;
	for(auto nxt:tree[now]){
		if(del[nxt])continue;
		ch.push_back(nxt);
	}
	del[now] = true;
	for(int i = 1;i<ch.size();i+=2){
		int a = ch[i-1],b = ch[i];
		int r = ask(a,b,tar);
		if(r == now)continue;
		else if(r == a)calc(a,tar);
		else if(r == b)calc(b,tar);
		else if(r == tar){
			int tmp = ask(now,a,tar);
			if(tmp == now){
				del_edge(now,b);
				add_edge(now,tar);
				add_edge(tar,b);
			}
			else{
				del_edge(now,a);
				add_edge(now,tar);
				add_edge(tar,a);
			}
		}
		else{
			int tmp = ask(now,r,a);
			if(tmp == now){
				done[r] = true;
				del_edge(now,b);
				add_edge(now,r);
				add_edge(r,b);
				add_edge(r,tar);
			}
			else{
				done[r] = true;
				del_edge(now,a);
				add_edge(now,r);
				add_edge(r,a);
				add_edge(r,tar);
			}
		}
		return;
	}
	if(ch.size()&1){
		auto a = ch.back();
		int r = ask(now,a,tar);
		if(r == now)add_edge(now,tar);
		else if(now == tar){
			del_edge(now,a);
			add_edge(now,tar);
			add_edge(tar,a);
		}
		else if(r == a)calc(a,tar);
		else{
			done[r] = true;
			del_edge(now,a);
			add_edge(now,r);
			add_edge(r,a);
			add_edge(r,tar);
		}
		return;
	}
	add_edge(now,tar);
	return;
}

void addpt(int tar){
	del.reset();
	calc(0,tar);
	done[tar] = true;
}
void answer(){
	for(int i = 0;i<N;i++){
		for(auto nx:tree[i]){
			if(nx>i)Bridge(i,nx);
		}
	}
	return;
}
void print(){
	for(int i = 0;i<N;i++){
		for(auto nx:tree[i]){
			if(nx>i)cout<<i<<":"<<nx<<endl;
		}
	}
	return;
}

void Solve(int NN) {
	N = NN;
	srand(time(NULL));
	for(int i = 0;i<N;i++)perm.push_back(i);
	//random_shuffle(perm.begin(),perm.end());
	done[0] = true;
	for(auto &i:perm)if(!done[i])addpt(i);
	//print();
	answer();
	cerr<<"HI"<<endl;
	return;
}

Compilation message

meetings.cpp: In function 'void calc(int, int)':
meetings.cpp:89:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i = 1;i<ch.size();i+=2){
      |                ~^~~~~~~~~~
meetings.cpp:70:13: warning: 'nx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |   else if(r == nx||r == now){
      |           ~~^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Incorrect 1 ms 344 KB Wrong Answer [1]
15 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Incorrect 1 ms 344 KB Wrong Answer [1]
15 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 597 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -