Submission #1185076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185076		mertbbm	Amusement Park (JOI17_amusement_park)	C++20	0 / 100	4027 ms	30836 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

//MessageBoard(index,val)
struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	int get(int x){
		return e[x]<0?x:e[x]=get(e[x]);
	}
	bool unite(int x, int y){
		x=get(x); y=get(y);
		if(x==y) return 1;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 0;
	}
};

int visited[10005];
int bit[10005];
vector<int>adj[10005];
set<int>se;
vector<int>storage;
int lst=0;

void dfs(int index, int sz){
	if((int)storage.size()==sz) return;
	visited[index]=lst+1;
	storage.push_back(index);
	if(lst==0) bit[index]=storage.size()-1;
	se.erase(bit[index]);
	if((int)storage.size()==sz) return;
	for(auto it:adj[index]){
		if(visited[it]!=lst) continue;
		dfs(it,sz);
	}
}

void Joi(int32_t n, int32_t m, int32_t a[], int32_t b[], long long val, int32_t t){
	DSU dsu;
	dsu.init(n+5);
	for(int x=0;x<m;x++){
		if(dsu.unite(a[x],b[x])) continue;
		adj[a[x]].push_back(b[x]);
		adj[b[x]].push_back(a[x]);
	}
	
	queue<pii>q;
	q.push({0,0});
	
	//show(done,1);
	while(!q.empty()){
		pii cur=q.front();
		q.pop();
		se.clear();
		storage.clear();
		for(int y=0;y<60;y++) se.insert(y);
		dfs(cur.first,cur.second==0?60:59);
		visited[cur.second]=lst+1;
		if(cur.second!=0)bit[cur.second]=*se.begin();
		for(auto index:storage){
			for(auto it:adj[index]){
				if(visited[it]==0){
					q.push({index,it});
				}
			}
		}
		lst++;
	}
	
	for(int x=0;x<n;x++){
		int a=0;
		if(val&(1LL<<bit[x])) a=1;
		MessageBoard(x,a);
	}

}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

//MessageBoard(index,val)
struct DSU{
	vector<int>e;
	void init(int n){
		e=vector<int>(n,-1);
	}
	int get(int x){
		return e[x]<0?x:e[x]=get(e[x]);
	}
	bool unite(int x, int y){
		x=get(x); y=get(y);
		if(x==y) return 1;
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y];
		e[y]=x;
		return 0;
	}
};

int visited[10005];
int bit[10005];
vector<int>adj[10005];
set<int>se;
vector<int>storage;
vector<int>path;
int lst=0;

void dfs(int index, int sz, int par){
	if((int)storage.size()==sz) return;
	if(par!=-1)path.push_back(index);
	visited[index]=lst+1;
	storage.push_back(index);
	if(lst==0) bit[index]=storage.size()-1;
	se.erase(bit[index]);
	if((int)storage.size()==sz) return;
	for(auto it:adj[index]){
		if(visited[it]!=lst) continue;
		dfs(it,sz,index);
	}
	if(par!=-1) path.push_back(par);
}

long long Ioi(int32_t n, int32_t m, int32_t a[], int32_t b[], int32_t p, int32_t v, int32_t t){
	DSU dsu;
	dsu.init(n+5);
	for(int x=0;x<m;x++){
		if(dsu.unite(a[x],b[x])) continue;
		adj[a[x]].push_back(b[x]);
		adj[b[x]].push_back(a[x]);
	}
	
	queue<pii>q;
	q.push({0,0});
	
	int ret=0;
	
	while(!q.empty()){
		pii cur=q.front();
		q.pop();
		se.clear();
		storage.clear();
		path.clear();
		for(int y=0;y<60;y++) se.insert(y);
		dfs(cur.first,cur.second==0?60:59,-1);
		visited[cur.second]=lst+1;
		if(cur.second!=0){
			bit[cur.second]=*se.begin();
			storage.push_back(cur.second);
		}
		//check
		bool amos=false;
		for(auto it:storage){
			if(it==p) amos=true;
		}
		if(amos){
			int arr[60];
			for(auto it:path){
				int a=Move(it);
				arr[bit[it]]=a;
			}
			for(int y=0;y<60;y++){
				ret+=arr[y]*(1LL<<y);
			}
			return ret;
		}
		for(auto index:storage){
			for(auto it:adj[index]){
				if(visited[it]==0){
					q.push({index,it});
				}
			}
		}
		lst++;
	}
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17