oj.uz

Submission #60381

# Submission time Handle Problem Language Result Execution time Memory
60381 2018-07-24T04:25:15 Z Benq Amusement Park (JOI17_amusement_park) C++14
100 / 100
 81 ms 36400 KB 
#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;
}
*/
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13668 KB Output is correct
2 Correct 18 ms 14856 KB Output is correct
3 Correct 22 ms 14920 KB Output is correct
4 Correct 22 ms 14928 KB Output is correct
5 Correct 23 ms 14936 KB Output is correct
6 Correct 23 ms 14948 KB Output is correct
7 Correct 20 ms 15028 KB Output is correct
8 Correct 19 ms 15212 KB Output is correct
9 Correct 19 ms 15332 KB Output is correct
10 Correct 18 ms 15356 KB Output is correct
11 Correct 24 ms 15444 KB Output is correct
12 Correct 24 ms 15520 KB Output is correct
13 Correct 22 ms 15588 KB Output is correct
14 Correct 20 ms 15680 KB Output is correct
15 Correct 22 ms 15716 KB Output is correct
16 Correct 22 ms 15780 KB Output is correct
17 Correct 20 ms 15852 KB Output is correct
18 Correct 23 ms 15940 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 17064 KB Output is correct
2 Correct 57 ms 18280 KB Output is correct
3 Correct 60 ms 18632 KB Output is correct
4 Correct 43 ms 18824 KB Output is correct
5 Correct 41 ms 19012 KB Output is correct
6 Correct 41 ms 19200 KB Output is correct
7 Correct 49 ms 19264 KB Output is correct
8 Correct 41 ms 19424 KB Output is correct
9 Correct 43 ms 19616 KB Output is correct
10 Correct 38 ms 19712 KB Output is correct
11 Correct 44 ms 19784 KB Output is correct
12 Correct 44 ms 19856 KB Output is correct
13 Correct 41 ms 19888 KB Output is correct
14 Correct 41 ms 20020 KB Output is correct
15 Correct 41 ms 20224 KB Output is correct
16 Correct 39 ms 20424 KB Output is correct
17 Correct 49 ms 20616 KB Output is correct
18 Correct 41 ms 20808 KB Output is correct
19 Correct 48 ms 21000 KB Output is correct
20 Correct 38 ms 21576 KB Output is correct
21 Correct 31 ms 22152 KB Output is correct
22 Correct 40 ms 22248 KB Output is correct
23 Correct 53 ms 22312 KB Output is correct
24 Correct 39 ms 22472 KB Output is correct
25 Correct 44 ms 22664 KB Output is correct
26 Correct 42 ms 22856 KB Output is correct
27 Correct 50 ms 23176 KB Output is correct
28 Correct 71 ms 23404 KB Output is correct
29 Correct 40 ms 23448 KB Output is correct
30 Correct 40 ms 23584 KB Output is correct
31 Correct 22 ms 23680 KB Output is correct
32 Correct 23 ms 23680 KB Output is correct
33 Correct 18 ms 23680 KB Output is correct
34 Correct 22 ms 23680 KB Output is correct
35 Correct 18 ms 23680 KB Output is correct
36 Correct 20 ms 23680 KB Output is correct
37 Correct 19 ms 23680 KB Output is correct
38 Correct 19 ms 23680 KB Output is correct
39 Correct 18 ms 23680 KB Output is correct
40 Correct 23 ms 23680 KB Output is correct
41 Correct 22 ms 23680 KB Output is correct
42 Correct 23 ms 23680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23680 KB Output is correct
2 Correct 19 ms 23680 KB Output is correct
3 Correct 19 ms 23680 KB Output is correct
4 Correct 22 ms 23680 KB Output is correct
5 Correct 24 ms 23680 KB Output is correct
6 Correct 28 ms 23680 KB Output is correct
7 Correct 23 ms 23680 KB Output is correct
8 Correct 23 ms 23680 KB Output is correct
9 Correct 40 ms 24220 KB Output is correct
10 Correct 40 ms 24904 KB Output is correct
11 Correct 39 ms 25144 KB Output is correct
12 Correct 19 ms 25240 KB Output is correct
13 Correct 19 ms 25240 KB Output is correct
14 Correct 22 ms 25240 KB Output is correct
15 Correct 19 ms 25240 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 25240 KB Output is correct
2 Correct 62 ms 25240 KB Output is correct
3 Correct 52 ms 25380 KB Output is correct
4 Correct 42 ms 25520 KB Output is correct
5 Correct 50 ms 25836 KB Output is correct
6 Correct 40 ms 26152 KB Output is correct
7 Correct 45 ms 26216 KB Output is correct
8 Correct 45 ms 26280 KB Output is correct
9 Correct 43 ms 26344 KB Output is correct
10 Correct 48 ms 26408 KB Output is correct
11 Correct 47 ms 26480 KB Output is correct
12 Correct 48 ms 26552 KB Output is correct
13 Correct 48 ms 26584 KB Output is correct
14 Correct 50 ms 26716 KB Output is correct
15 Correct 55 ms 26920 KB Output is correct
16 Correct 46 ms 27124 KB Output is correct
17 Correct 44 ms 27316 KB Output is correct
18 Correct 49 ms 27636 KB Output is correct
19 Correct 51 ms 27864 KB Output is correct
20 Correct 34 ms 28312 KB Output is correct
21 Correct 39 ms 28856 KB Output is correct
22 Correct 44 ms 28952 KB Output is correct
23 Correct 43 ms 29016 KB Output is correct
24 Correct 49 ms 29176 KB Output is correct
25 Correct 39 ms 29368 KB Output is correct
26 Correct 52 ms 29560 KB Output is correct
27 Correct 39 ms 29880 KB Output is correct
28 Correct 43 ms 30104 KB Output is correct
29 Correct 39 ms 30228 KB Output is correct
30 Correct 45 ms 30412 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 30576 KB Output is correct
2 Correct 58 ms 30864 KB Output is correct
3 Correct 52 ms 31240 KB Output is correct
4 Correct 49 ms 31432 KB Output is correct
5 Correct 50 ms 31876 KB Output is correct
6 Correct 48 ms 32320 KB Output is correct
7 Correct 50 ms 32320 KB Output is correct
8 Correct 41 ms 32320 KB Output is correct
9 Correct 47 ms 32320 KB Output is correct
10 Correct 41 ms 32320 KB Output is correct
11 Correct 43 ms 32420 KB Output is correct
12 Correct 38 ms 32520 KB Output is correct
13 Correct 40 ms 32584 KB Output is correct
14 Correct 46 ms 32696 KB Output is correct
15 Correct 41 ms 32844 KB Output is correct
16 Correct 50 ms 33072 KB Output is correct
17 Correct 52 ms 33380 KB Output is correct
18 Correct 41 ms 33596 KB Output is correct
19 Correct 40 ms 33708 KB Output is correct
20 Correct 38 ms 34208 KB Output is correct
21 Correct 38 ms 34712 KB Output is correct
22 Correct 53 ms 34848 KB Output is correct
23 Correct 47 ms 35000 KB Output is correct
24 Correct 45 ms 35192 KB Output is correct
25 Correct 38 ms 35384 KB Output is correct
26 Correct 47 ms 35520 KB Output is correct
27 Correct 44 ms 35844 KB Output is correct
28 Correct 41 ms 36224 KB Output is correct
29 Correct 37 ms 36320 KB Output is correct
30 Correct 38 ms 36360 KB Output is correct
31 Correct 19 ms 36400 KB Output is correct
32 Correct 22 ms 36400 KB Output is correct
33 Correct 19 ms 36400 KB Output is correct
34 Correct 23 ms 36400 KB Output is correct
35 Correct 20 ms 36400 KB Output is correct
36 Correct 19 ms 36400 KB Output is correct
37 Correct 18 ms 36400 KB Output is correct
38 Correct 22 ms 36400 KB Output is correct
39 Correct 17 ms 36400 KB Output is correct
40 Correct 19 ms 36400 KB Output is correct
41 Correct 20 ms 36400 KB Output is correct
42 Correct 24 ms 36400 KB Output is correct