Submission #122855

#	Time	Username	Problem	Language	Result	Execution time	Memory
122855		tjd229	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	58 ms	10992 KiB

Joi

#include "Joi.h"
#include <memory.h>
#include <vector>
using namespace std;
int wpos[10000];
vector<int> jedge[10000];
vector<int> jg[10000];
int jp[10000][15],jd[10000];
//climb
//lca
//dist
int jclimb(int x,int d) {
	int step = 0;
	while (d) {
		if (d & 1) x = jp[x][step];
		d >>= 1;
		++step;
	}
	return x;
}
int jlca(int a,int b) {
	if (jd[a] < jd[b]) b = jclimb(b,jd[b]-jd[a]);
	else if (jd[a] > jd[b]) a = jclimb(a,jd[a]-jd[b]);
	if (a == b) return a;
	for (int j = 14; j >= 0; --j) {
		if (jp[a][j] != jp[b][j]) {
			a = jp[a][j];
			b = jp[b][j];
		}
	}
	return jp[a][0];
}
inline int jdist(int a,int b) {
	return jd[a] + jd[b] - (jd[jlca(a,b)]<<1);
}
void make_jtree(int x,vector<int> &g) {//init dfs
	if (g.size() < 60) g.push_back(x);
	wpos[x] = -1;
	for (auto to : jedge[x]) {
		if (wpos[to] < 0) continue;
		jd[to] = jd[x] + 1;
		jp[to][0] = x;
		make_jtree(to, g);
	}	
}
void jdfs(int x) {
	if (wpos[x]!=-1) return;
	int p = jp[x][0];
	jdfs(p);
	jg[x] = jg[p];
	int mx = 0;
	int rep = 0;
	for (int i = 0; i < jg[x].size(); ++i) {
		if (jg[x][i] == p) continue;
		int dist = jdist(x,jg[x][i]);
		if (dist >mx) {
			mx = dist;
			rep = i;
		}
	}
	wpos[x] = wpos[jg[x][rep]];
	jg[x][rep] = x;	
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
	memset(jp,-1,sizeof(jp));
	for (int i = 0; i < M; ++i) {
		jedge[A[i]].push_back(B[i]);
		jedge[B[i]].push_back(A[i]);
	}
	make_jtree(0,jg[0]);
	for (int i = 0; i < jg[0].size(); ++i) {
		int x = jg[0][i];
		jg[x] = jg[0];
		wpos[x] = i;
	}
	for (int j = 1; j < 15; ++j) for (int i = 0; i < N; ++i) jp[i][j] = jp[jp[i][j - 1]][j - 1];

	for (int i = 0; i < N; ++i) {
		jdfs(i);
		MessageBoard(i,(X>>wpos[i])&1);
	}

}

Ioi

#include "Ioi.h"
#include <vector>
#include <memory.h>
using namespace std;
int rpos[10000];
vector<int> iedge[10000];
vector<int> ig[10000];
int ip[10000][15], id[10000];
int vis[10000];

int iclimb(int x, int d) {
	int step = 0;
	while (d) {
		if (d & 1) x = ip[x][step];
		d >>= 1;
		++step;
	}
	return x;
}
int ilca(int a, int b) {
	if (id[a] < id[b]) b = iclimb(b, id[b] - id[a]);
	else if (id[a] > id[b]) a = iclimb(a, id[a] - id[b]);
	if (a == b) return a;
	for (int j = 14; j >= 0; --j) {
		if (ip[a][j] != ip[b][j]) {
			a = ip[a][j];
			b = ip[b][j];
		}
	}
	return ip[a][0];
}
inline int idist(int a, int b) {
	return id[a] + id[b] - (id[ilca(a, b)] << 1);
}
void make_itree(int x, vector<int> &g) {//init dfs
	if (g.size() < 60) g.push_back(x);
	rpos[x] = -1;
	for (int i = 0; i < iedge[x].size(); ++i) {
		int to = iedge[x][i];
		if (rpos[to] < 0) {
			iedge[x][i] = -1;
			continue;
		}
		
		id[to] = id[x] + 1;
		ip[to][0] = x;
		make_itree(to, g);
	}

}
void idfs(int x) {
	if (rpos[x] != -1) return;
	
	int p = ip[x][0];
	idfs(p);
	ig[x] = ig[p];
	int mx = 0;
	int rep = 0;
	for (int i = 0; i < ig[x].size(); ++i) {
		if (ig[x][i] == p) continue;
		int dist = idist(x, ig[x][i]);
		if (dist > mx) {
			mx = dist;
			rep = i;
		}
	}
	rpos[x] = rpos[ig[x][rep]];
	ig[x][rep] = x;
}
long long cage(int x,int from) {
	long long mem = 0;
	//printf("dfs:%d\n",x);
	for (auto to : iedge[x]) {
		if (to < 0 || to==from) continue;
		if (!vis[to]) continue;
		long long r = Move(to);
		mem |= (r <<rpos[to]);
		mem |= cage(to,x);
		//printf("dfs:%d\n", x);
	}
	int p = ip[x][0];
	if (p>=0 && vis[p] && p!=from) {
		int p = ip[x][0];
		long long r = Move(p);
		mem |= (r << rpos[p]);
		mem |= cage(p,x);
		//printf("dfs:%d\n", x);
	}
	vis[x] = 0;
	if (from >= 0) {
		long long r = Move(from);
		mem |= (r << rpos[from]);
	}
	return mem;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	memset(ip, -1, sizeof(ip));
	for (int i = 0; i < M; ++i) {
		iedge[A[i]].push_back(B[i]);
		iedge[B[i]].push_back(A[i]);
	}
	make_itree(0, ig[0]);
	for (int i = 0; i < ig[0].size(); ++i) {
		int x = ig[0][i];
		ig[x] = ig[0];
		rpos[x] = i;
	}
	
	for (int j = 1; j < 15; ++j) for (int i = 0; i < N; ++i) ip[i][j] = ip[ip[i][j - 1]][j - 1];
	idfs(P);
	for (auto x : ig[P]) vis[x] = 1;
	
	return cage(P, -1);
}

Compilation message (stderr)

Joi.cpp: In function 'void jdfs(int)':
Joi.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < jg[x].size(); ++i) {
                  ~~^~~~~~~~~~~~~~
Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < jg[0].size(); ++i) {
                  ~~^~~~~~~~~~~~~~

Ioi.cpp: In function 'void make_itree(int, std::vector<int>&)':
Ioi.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < iedge[x].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~~~
Ioi.cpp: In function 'void idfs(int)':
Ioi.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ig[x].size(); ++i) {
                  ~~^~~~~~~~~~~~~~
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ig[0].size(); ++i) {
                  ~~^~~~~~~~~~~~~~

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