Submission #125625

#	Time	Username	Problem	Language	Result	Execution time	Memory
125625		Retro3014	Amusement Park (JOI17_amusement_park)	C++17	10 / 100	3055 ms	262148 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 10000;
const int MAX_M = 20000;

vector<int> grpa[MAX_N+1];
vector<int> grp2[MAX_N+1];

int nmb[MAX_N+1];
int pa[MAX_N+1];

int chc[MAX_N+1];
int dgr[MAX_N+1];

set<int> s;

int find_leafa(int x){
	for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
		dgr[*it] = 0;
	}
	for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
		int k = (*it);
		if(k==0)	continue;
		if(chc[pa[k]]){
			dgr[pa[k]]++;
			dgr[k]++;
		}
	}
	for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
		int k = (*it);
		if(dgr[k]==1 && k!=x)	return k;
	}
}

void dfsa(int x){
	int t = -1;
	if(s.size()==60){
		int lf = find_leafa(pa[x]);
		t = lf;
		s.erase(lf);
		chc[lf] = false;
		nmb[x] = nmb[lf];
		chc[x] = true;
		s.insert(x);
	}else if(s.size()==59){
		s.insert(x);
		chc[x] = true;
		int cnt = 0;
		for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
			nmb[*it] = cnt;
			cnt++;
		}
	}else{
		s.insert(x);
		chc[x] = true;
	}
	for(int i=0; i<grpa[x].size(); i++){
		if(grpa[x][i]==pa[x])	continue;
		pa[grpa[x][i]] = x;
		dfsa(grpa[x][i]);
	}
	if(t!=-1){
		s.erase(x);
		s.insert(t);
		chc[t] = true;
		chc[x] = false;
	}
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i=0; i<M; i++){
		grpa[A[i]].pb(B[i]); grpa[B[i]].pb(A[i]);
  	}
  	dfsa(0);
  	for(int i=0; i<N; i++){
  		ll t = ((ll)1<<nmb[i]);
  		MessageBoard(i, ((t & X)>0));
  		//cout<<i<<" "<<nmb[i]<<" "<<((t & X)>0)<<endl;
  		t*=2;
  	}
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 10000;
const int MAX_M = 20000;

vector<int> gp[MAX_N+1];
vector<int> gp2[MAX_N+1];

int num[MAX_N+1];
int p[MAX_N+1];

int chk[MAX_N+1];
int deg[MAX_N+1];

set<int> st;

int find_leaf(int x){
	for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
		deg[*it] = 0;
	}
	for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
		int k = (*it);
		if(k==0)	continue;
		if(chk[p[k]]){
			deg[p[k]]++;
			deg[k]++;
		}
	}
	for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
		int k = (*it);
		if(deg[k]==1 && k!=x)	return k;
	}
}

bool found = false;

int pos;

void dfs(int x){
	int t = -1;
	if(st.size()==60){
		int lf = find_leaf(p[x]);
		t = lf;
		st.erase(lf);
		chk[lf] = false;
		num[x] = num[lf];
		chk[x] = true;
		st.insert(x);
		if(x==pos){
			found = true;
			return;
		}
	}else if(st.size()==59){
		st.insert(x);
		chk[x] = true;
		int cnt = 0;
		for(set<int>::iterator it = st.begin(); it!=st.end(); it++){
			num[*it] = cnt;
			cnt++;
		}
		if(st.find(pos)!=st.end()){
			found = true;
			return;
		}
	}else{
		st.insert(x);
		chk[x] = true;
	}
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i]==p[x])	continue;
		p[gp[x][i]] = x;
		dfs(gp[x][i]);
		if(found)	return;
	}
	if(t!=-1){
		st.erase(x);
		st.insert(t);
		chk[t] = true;
		chk[x] = false;
	}
}


bool vst[MAX_N+1];
int ans[100];

void calc(int x){
	vst[x] = true;
	for(int i=0; i<gp[x].size(); i++){
		if(chk[gp[x][i]] && !vst[gp[x][i]]){
			int t = Move(gp[x][i]);
			ans[num[gp[x][i]]] = t;
			calc(gp[x][i]);
			Move(x);
		}
	}
}



long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	pos = P;
	for(int i=0; i<M; i++){
		gp[A[i]].pb(B[i]); gp[B[i]].pb(A[i]);
  	}
  	dfs(0);
  	ans[num[P]] = V;
  	calc(P);
  	ll answer=0;
  	ll t = 1;
  	for(int i=0; i<60; i++){
  		answer += (ll)ans[i] * t;
  		t*=2;
  	}
  	//cout<<answer<<endl;
  	return answer;
}

Compilation message (stderr)

Joi.cpp: In function 'void dfsa(int)':
Joi.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<grpa[x].size(); i++){
               ~^~~~~~~~~~~~~~~
Joi.cpp: In function 'int find_leafa(int)':
Joi.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Ioi.cpp: In function 'void dfs(int)':
Ioi.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
Ioi.cpp: In function 'void calc(int)':
Ioi.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
Ioi.cpp: In function 'int find_leaf(int)':
Ioi.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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