oj.uz

Submission #914207

# Submission time Handle Problem Language Result Execution time Memory
914207 2024-01-21T10:59:35 Z YassirSalama ICC (CEOI16_icc) C++17
90 / 100
 106 ms 668 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include<assert.h>
#include <functional>
#include <iterator>
#include "icc.h"
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
int ask(vector<int> a,vector<int> b){
	int n=a.size();
	int m=b.size();
	int A[n];
	int B[m];
	for(int i=0;i<n;i++) A[i]=a[i];
	for(int i=0;i<m;i++) B[i]=b[i];
	return query(n,m,A,B);
}
const int MAXN=2e2+100;
int par[MAXN];
vector<vector<int>> v(MAXN);
struct DSU {
	DSU(){
		for(int i=0;i<MAXN;i++) {
			par[i]=i;
			v[i].pb(i);
		}
	}
	int find(int node){
		return node==par[node]?node:par[node]=find(par[node]);
	}
	bool same(int a,int b){
		return find(a)==find(b);
	}
	void merge(int a,int b){
		a=find(a);
		b=find(b);
		if(a==b) return;
		if(v[a].size()<v[b].size()) swap(a,b);
		for(auto x:v[b]) v[a].pb(x);
		v[b].clear();
		par[b]=a;
	}
};
int n;
DSU dsu=DSU();
pair<int,int> dnc(vector<int> a,vector<int> b,int n,int m){
	if(n==1&&m==1) {
		return {a[0],b[0]};
	}
	vector<int> c,d;
	int mid=n/2;
	for(int i=0;i<mid;i++){
		c.pb(a[i]);
	}
	for(int i=mid;i<n;i++) d.pb(a[i]);
	if(c.size()&&ask(b,c)){
		int mid=m/2;
		vector<int> x,y;
		for(int i=0;i<mid;i++) x.pb(b[i]);
		for(int i=mid;i<m;i++) y.pb(b[i]);
		if(x.size()&&ask(c,x)) return dnc(x,c,x.size(),c.size());
		else return dnc(y,c,y.size(),c.size());
	}
	else{
		int mid=m/2;
		vector<int> x,y;
		for(int i=0;i<mid;i++) x.pb(b[i]);
		for(int i=mid;i<m;i++) y.pb(b[i]);
		if(x.size()&&ask(d,x)) return dnc(x,d,x.size(),d.size());
		else return dnc(y,d,y.size(),d.size());
	}

	return {0,0};
}
void solve(){
	set<int> d;
	for(int i=1;i<=n;i++) d.insert(dsu.find(i));
	vector<pair<vector<int>,vector<int>>> sets;
    for(int bit=0;bit<=log2(n);bit++){
    	vector<int> a,b;
    	for(auto x:d){
    		if(x&(1<<bit)) {
    			for(auto y:v[x]){
    				a.push_back(y);
    				continue;
    			}
    		}
    		else {
    			for(auto y:v[x]){
    				b.push_back(y);
    			}
    		}
    	}
    	sets.push_back({a,b});
    }
    for(auto x:sets){
    	vector<int> a=x.F,b=x.S;
    	if(ask(a,b)){
    		//there is a road between those 2 sets
    		pair<int,int> c=dnc(a,b,a.size(),b.size());
    		int x=c.F;
    		int y=c.S;
    		// dbg(x,y)
    		setRoad(x,y);
    		dsu.merge(x,y);
    		return;
    	}
    }
}
void run(int N){
	n=N;
	for(int wwww=0;wwww<n-1;wwww++){
		solve();
	}
}

#ifdef IOI
int main(){
	int n;
	cin>>n;
	vector<pair<int,int>> v;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		v.pb({a,b});
	}
	for(int i=0;i<MMS;i++) pr[i]=i;
	EDGES=v;
	mp[{EDGES[0].F,EDGES[0].S}]=1;
	mp[{EDGES[0].S,EDGES[0].F}]=1;

	merge(EDGES[0].F,EDGES[0].S);
 	run(n);
 	cout<<"YES"<<endl;
}
#endif

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Ok! 99 queries used.
2 Correct 5 ms 604 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 656 KB Ok! 534 queries used.
2 Correct 37 ms 604 KB Ok! 691 queries used.
3 Correct 31 ms 600 KB Ok! 681 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 600 KB Ok! 1379 queries used.
2 Correct 95 ms 600 KB Ok! 1691 queries used.
3 Correct 75 ms 600 KB Ok! 1347 queries used.
4 Correct 101 ms 668 KB Ok! 1530 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 600 KB Ok! 1383 queries used.
2 Correct 83 ms 656 KB Ok! 1459 queries used.
3 Correct 93 ms 664 KB Ok! 1644 queries used.
4 Correct 81 ms 660 KB Ok! 1343 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 664 KB Ok! 1639 queries used.
2 Correct 106 ms 652 KB Ok! 1680 queries used.
3 Correct 94 ms 652 KB Ok! 1684 queries used.
4 Correct 94 ms 648 KB Ok! 1616 queries used.
5 Correct 81 ms 604 KB Ok! 1431 queries used.
6 Correct 92 ms 600 KB Ok! 1619 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 656 KB Too many queries! 1638 out of 1625
2 Halted 0 ms 0 KB -