Submission #60381

#	Time	Username	Problem	Language	Result	Execution time	Memory
60381		Benq	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	81 ms	36400 KiB

Joi

#include "Joi.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

/*#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

void Joi(int N, int M, int A[], int B[], long long X, int T);
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);

static int N, M, A[MMAX], B[MMAX], P, T;
static long long X;
static int given_msg[NMAX];
static int pos, n_move;
static set<pair<int, int> > edges;

void WrongAnswer(int e)
{
	printf("Wrong Answer[%d]\n", e);
	exit(0);
}*/

bitset<60> cbit;
int cpos[MX], par[MX], ok[60];

/*void MessageBoard(int attr, int msg)
{
	if (!(0 <= attr && attr <= N - 1)) {
		WrongAnswer(1);
	}
	if (given_msg[attr] != -1) {
		WrongAnswer(2);
	}
	if (!(msg == 0 || msg == 1)) {
		WrongAnswer(3);
	}
	given_msg[attr] = msg;
}

int Move(int dest)
{
    ok[cpos[dest]] = 1;
    // cout << "AH " << cpos[dest] << "\n";
	if (!(0 <= dest && dest <= N - 1)) {
		WrongAnswer(6);
	}
	if (!edges.count({ pos, dest })) {
		WrongAnswer(7);
	}
	++n_move;
	if (n_move > MOVEMAX) {
		WrongAnswer(8);
	}
	pos = dest;
	return given_msg[pos];
}*/

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;
vi adj[MX], ADJ[MX], path[60], v;

void dfs(int a, int b) {
	v.pb(a);
	for (int i: adj[a]) if (i != b) dfs(i,a);
}

void dfs2(int a, int ori, int pos) {
	cpos[a] = cpos[path[ori][pos]];
    // cout << "OOH " << a << "\n";
	for (int i: adj[a]) if (cpos[i] == -1) {
		par[i] = a;
		dfs2(i,ori,(pos+sz(path[ori])-1)%sz(path[ori]));
	}
}

void genPath(vi& v, int cur, int pre) {
	v.pb(cur);
	for (int i: ADJ[cur]) if (i != pre) {
		genPath(v,i,cur);
		v.pb(cur);
	}
}

void gen(int N, int M, int A[], int B[]) {
	F0R(i,M) if (D.unite(A[i],B[i])) 
		adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);

	dfs(0,-1);
	v.resize(60); 
	F0R(i,MX) cpos[i] = -1;
	F0R(i,60) {
	    // cout << "BLAH " << i << " " << v[i] << "\n";
	    cpos[v[i]] = i;
	}
	F0R(i,N) if (cpos[i] != -1) for (int j: adj[i]) if (cpos[j] != -1) ADJ[i].pb(j);

	F0R(i,60) {
		genPath(path[i],v[i],-1);
		// cout << "OOPS " << sz(path[i]) << "\n"; 
		/*cout << v[i] << " " << sz(path[i]) << "\n";
		for (int k: path[i]) cout << k << " ";
		cout << "\n";*/
		par[v[i]] = v[i];
		dfs2(v[i],i,0);
	}
}

void solve0(int N, ll X) {
	F0R(i,60) if (X&(1LL<<i)) cbit[i] = 1;
	F0R(i,N) MessageBoard(i, cbit[cpos[i]]);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	gen(N,M,A,B);
	solve0(N,X);
}

/*ll solve1(int P, int V) {
	cbit[cpos[P]] = V;
	vi tmp;
	// cout << "OOPS " << P << " " << V << " " << cpos[P] << "\n";
	F0R(i,120) {
	    // cout << "HUH " << P << " " << par[P] << "\n";
		if (sz(tmp)) {
			cbit[cpos[tmp.back()]] = Move(tmp.back());
			tmp.pop_back();
			if (sz(tmp) == 0) break;
		} else {
			if (par[P] == P) {
				tmp = path[cpos[P]];
				// cout << "OH " << sz(tmp) << "\n";
				reverse(all(tmp)); tmp.pop_back();
			} else {
				cbit[cpos[par[P]]] = Move(par[P]);
				P = par[P];
			}
		}
	}
	ll ans = 0;
	F0R(i,60) if (cbit[i] == 1) ans ^= 1LL<<i;
	return ans;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    D = DSU<MX>();
    F0R(i,MX) cpos[i] = par[i] = 0;
    F0R(i,MX) adj[i].clear(), ADJ[i].clear();
    F0R(i,60) path[i].clear(); 
    v.clear();
    cbit.reset();
	gen(N,M,A,B);
	return solve1(P,V);
}*/

/*

int main(void)
{
	int i;
	long long max_code;

	scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
	for (int i = 0; i < M; ++i) {
		scanf("%d%d", &(A[i]), &(B[i]));
		edges.insert({ A[i], B[i] });
		edges.insert({ B[i], A[i] });
	}
	for (int i = 0; i < N; ++i) {
		given_msg[i] = -1;
	}

	Joi(N, M, A, B, X, T);

	for (i = 0; i < N; ++i) {
		if (given_msg[i] == -1) {
			WrongAnswer(4);
		}
		// cout << given_msg[i] << " ";
	}
	
    // exit(0);
	n_move = 0;
	pos = P;
	long long answer = Ioi(N, M, A, B, P, given_msg[P], T);

    cout << answer << " " << X << "\n";
    F0R(i,60) cout << ok[i];
	if (answer != X) {
		WrongAnswer(5);
	}

	printf("Accepted : #move=%d\n", n_move);
	return 0;
}
*/

Ioi

#include "Ioi.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

/*#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

void Joi(int N, int M, int A[], int B[], long long X, int T);
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T);

static int N, M, A[MMAX], B[MMAX], P, T;
static long long X;
static int given_msg[NMAX];
static int pos, n_move;
static set<pair<int, int> > edges;

void WrongAnswer(int e)
{
	printf("Wrong Answer[%d]\n", e);
	exit(0);
}*/

bitset<60> cbit;
int cpos[MX], par[MX], ok[60];

/*void MessageBoard(int attr, int msg)
{
	if (!(0 <= attr && attr <= N - 1)) {
		WrongAnswer(1);
	}
	if (given_msg[attr] != -1) {
		WrongAnswer(2);
	}
	if (!(msg == 0 || msg == 1)) {
		WrongAnswer(3);
	}
	given_msg[attr] = msg;
}

int Move(int dest)
{
    ok[cpos[dest]] = 1;
    // cout << "AH " << cpos[dest] << "\n";
	if (!(0 <= dest && dest <= N - 1)) {
		WrongAnswer(6);
	}
	if (!edges.count({ pos, dest })) {
		WrongAnswer(7);
	}
	++n_move;
	if (n_move > MOVEMAX) {
		WrongAnswer(8);
	}
	pos = dest;
	return given_msg[pos];
}*/

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;
vi adj[MX], ADJ[MX], path[60], v;

void dfs(int a, int b) {
	v.pb(a);
	for (int i: adj[a]) if (i != b) dfs(i,a);
}

void dfs2(int a, int ori, int pos) {
	cpos[a] = cpos[path[ori][pos]];
    // cout << "OOH " << a << "\n";
	for (int i: adj[a]) if (cpos[i] == -1) {
		par[i] = a;
		dfs2(i,ori,(pos+sz(path[ori])-1)%sz(path[ori]));
	}
}

void genPath(vi& v, int cur, int pre) {
	v.pb(cur);
	for (int i: ADJ[cur]) if (i != pre) {
		genPath(v,i,cur);
		v.pb(cur);
	}
}

void gen(int N, int M, int A[], int B[]) {
	F0R(i,M) if (D.unite(A[i],B[i])) 
		adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);

	dfs(0,-1);
	v.resize(60); 
	F0R(i,MX) cpos[i] = -1;
	F0R(i,60) {
	    // cout << "BLAH " << i << " " << v[i] << "\n";
	    cpos[v[i]] = i;
	}
	F0R(i,N) if (cpos[i] != -1) for (int j: adj[i]) if (cpos[j] != -1) ADJ[i].pb(j);

	F0R(i,60) {
		genPath(path[i],v[i],-1);
		// cout << "OOPS " << sz(path[i]) << "\n"; 
		/*cout << v[i] << " " << sz(path[i]) << "\n";
		for (int k: path[i]) cout << k << " ";
		cout << "\n";*/
		par[v[i]] = v[i];
		dfs2(v[i],i,0);
	}
}

/*void solve0(int N, ll X) {
	F0R(i,60) if (X&(1LL<<i)) cbit[i] = 1;
	F0R(i,N) MessageBoard(i, cbit[cpos[i]]);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	gen(N,M,A,B);
	solve0(N,X);
}*/

ll solve1(int P, int V) {
	cbit[cpos[P]] = V;
	vi tmp;
	// cout << "OOPS " << P << " " << V << " " << cpos[P] << "\n";
	F0R(i,120) {
	    // cout << "HUH " << P << " " << par[P] << "\n";
		if (sz(tmp)) {
			cbit[cpos[tmp.back()]] = Move(tmp.back());
			tmp.pop_back();
			if (sz(tmp) == 0) break;
		} else {
			if (par[P] == P) {
				tmp = path[cpos[P]];
				// cout << "OH " << sz(tmp) << "\n";
				reverse(all(tmp)); tmp.pop_back();
			} else {
				cbit[cpos[par[P]]] = Move(par[P]);
				P = par[P];
			}
		}
	}
	ll ans = 0;
	F0R(i,60) if (cbit[i] == 1) ans ^= 1LL<<i;
	return ans;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    D = DSU<MX>();
    F0R(i,MX) cpos[i] = par[i] = 0;
    F0R(i,MX) adj[i].clear(), ADJ[i].clear();
    F0R(i,60) path[i].clear(); 
    v.clear();
    cbit.reset();
	gen(N,M,A,B);
	return solve1(P,V);
}

/*

int main(void)
{
	int i;
	long long max_code;

	scanf("%d%d%lld%d%d", &N, &M, &X, &P, &T);
	for (int i = 0; i < M; ++i) {
		scanf("%d%d", &(A[i]), &(B[i]));
		edges.insert({ A[i], B[i] });
		edges.insert({ B[i], A[i] });
	}
	for (int i = 0; i < N; ++i) {
		given_msg[i] = -1;
	}

	Joi(N, M, A, B, X, T);

	for (i = 0; i < N; ++i) {
		if (given_msg[i] == -1) {
			WrongAnswer(4);
		}
		// cout << given_msg[i] << " ";
	}
	
    // exit(0);
	n_move = 0;
	pos = P;
	long long answer = Ioi(N, M, A, B, P, given_msg[P], T);

    cout << answer << " " << X << "\n";
    F0R(i,60) cout << ok[i];
	if (answer != X) {
		WrongAnswer(5);
	}

	printf("Accepted : #move=%d\n", n_move);
	return 0;
}
*/

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