| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 914190 |
2024-01-21T10:38:18 Z |
YassirSalama |
ICC (CEOI16_icc) |
C++17 |
|
109 ms |
912 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();
int dnc(vector<int> a,vector<int> b,int n,int m){
if(n==1) return a[0];
int mid=(n)/2;
vector<int> c,d;
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(c,b)) return dnc(c,b,c.size(),m);
if(d.size()&&ask(d,b)) return dnc(d,b,d.size(),m);
return 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<=7;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
int x=dnc(a,b,a.size(),b.size());
// dbg(x);
int y=dnc(b,vector<int>(1,x),b.size(),1);
// 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
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
604 KB |
Ok! 182 queries used. |
| 2 |
Correct |
6 ms |
604 KB |
Ok! 158 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
604 KB |
Ok! 810 queries used. |
| 2 |
Correct |
36 ms |
604 KB |
Ok! 951 queries used. |
| 3 |
Correct |
38 ms |
604 KB |
Ok! 965 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
664 KB |
Too many queries! 2344 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
660 KB |
Too many queries! 2283 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
912 KB |
Too many queries! 2347 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
660 KB |
Too many queries! 2362 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
