Submission #60377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60377	2018-07-24T04:03:06 Z	Benq	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	142 ms	30680 KB

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);
}

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)
{
	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;
int cpos[MX], par[MX];
vi adj[MX], ADJ[MX], path[60], v;
bitset<60> cbit;

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) 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 << 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) {
		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]];
				reverse(all(tmp)); tmp.pop_back();
			} else {
			    // cout << "AH " << P << " " << par[P] << "\n";
				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();
	gen(N,M,A,B);
	return solve1(P,V);
}*/

Ioi

#include "Ioi.h"
// #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);
}

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)
{
	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;
int cpos[MX], par[MX];
vi adj[MX], ADJ[MX], path[60], v;
bitset<60> cbit;

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) 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 << 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) {
		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]];
				reverse(all(tmp)); tmp.pop_back();
			} else {
			    // cout << "AH " << P << " " << par[P] << "\n";
				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();
	gen(N,M,A,B);
	return solve1(P,V);
}

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	20 ms	14128 KB	Wrong Answer [7]
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	136 ms	28976 KB	Wrong Answer [7]
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	30072 KB	Output is correct
2	Correct	20 ms	30072 KB	Output is correct
3	Correct	23 ms	30072 KB	Output is correct
4	Correct	28 ms	30072 KB	Output is correct
5	Incorrect	26 ms	30072 KB	Wrong Answer [7]
6	Halted	0 ms	0 KB	-

Subtask #4

0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	142 ms	30072 KB	Wrong Answer [7]
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	138 ms	30680 KB	Wrong Answer [7]
2	Halted	0 ms	0 KB	-