oj.uz

Submission #255515

# Submission time Handle Problem Language Result Execution time Memory
255515 2020-08-01T07:11:16 Z b00n0rp Amusement Park (JOI17_amusement_park) C++17
100 / 100
 898 ms 13236 KB 
#include "Joi.h"
#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define F first
#define S second

static const int MX = 10005;

static vi g[MX],adj[MX];
static int par[MX],dep[MX];

static bitset<MX> vis;
static int n,ind[MX];

static vi subgraph[MX];

static vi cc;

static void findtree(int u){
	if(cc.size() < 60){
		ind[u] = cc.size();
		cc.pb(u);
	}
	vis[u] = 1;
	for(auto v:g[u]){
		if(!vis[v]){
			adj[u].pb(v);
			par[v] = u;
			dep[v] = 1+dep[u];
			findtree(v);
		}
	}
}

static void dfs(int u){
	if(ind[u] == -1){
		mii deg;
		for(auto x:subgraph[par[u]]){
			for(auto y:subgraph[par[u]]){
				if(binary_search(all(adj[x]),y)){
					deg[x]++;
					deg[y]++;
				}
			}
		}
		for(auto x:deg){
			if(x.S == 1 and x.F != par[u]){
				ind[u] = ind[x.F];
				for(auto y:subgraph[par[u]]){
					if(x.F != y) subgraph[u].pb(y);
				}
				subgraph[u].pb(u);
				break;
			}
		}
	}
	for(auto v:adj[u]){
		dfs(v);
	}
}

void Joi(int N, int M, int A[], int B[], long long X, int T){
	n = N;
	REP(i,M){
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	REP(i,n+2) ind[i] = -1;
	par[0] = 0;
	dep[0] = 0;
	findtree(0);
	for(auto x:cc) subgraph[x] = cc;
	REP(i,n) sort(all(adj[i]));
	dfs(0);
	REP(i,n) MessageBoard(i,((X>>ind[i])&1));
}

#include "Ioi.h"
#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define F first
#define S second

static const int MX = 10005;

static vi g[MX],adj[MX];
static int par[MX],dep[MX];

static bitset<MX> vis;
static int n,ind[MX];

static vi subgraph[MX];

static vi cc;

static void findtree(int u){
	if(cc.size() < 60){
		ind[u] = cc.size();
		cc.pb(u);
	}
	vis[u] = 1;
	for(auto v:g[u]){
		if(!vis[v]){
			adj[u].pb(v);
			par[v] = u;
			dep[v] = 1+dep[u];
			findtree(v);
		}
	}
}

static void dfs(int u){
	if(ind[u] == -1){
		mii deg;
		for(auto x:subgraph[par[u]]){
			for(auto y:subgraph[par[u]]){
				if(binary_search(all(adj[x]),y)){
					deg[x]++;
					deg[y]++;
				}
			}
		}
		for(auto x:deg){
			if(x.S == 1 and x.F != par[u]){
				ind[u] = ind[x.F];
				for(auto y:subgraph[par[u]]){
					if(x.F != y) subgraph[u].pb(y);
				}
				subgraph[u].pb(u);
				break;
			}
		}
	}
	for(auto v:adj[u]){
		dfs(v);
	}
}

static long long ans = 0;

static void calc(int u){
	vis[u] = 1;
	for(auto v:adj[u]){
		if(vis[v]) continue;
		if(!binary_search(all(cc),v)) continue;
		ans |= (1LL<<ind[v])*Move(v);
		calc(v);
		ans |= (1LL<<ind[u])*Move(u);
	}
	int v = par[u];
	if(vis[v]) return;
	if(!binary_search(all(cc),v)) return;
	ans |= (1LL<<ind[v])*Move(v);
	calc(v);
	ans |= (1LL<<ind[u])*Move(u);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	n = N;
	REP(i,M){
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	REP(i,n+2) ind[i] = -1;
	par[0] = 0;
	dep[0] = 0;
	findtree(0);
	for(auto x:cc) subgraph[x] = cc;
	REP(i,n) sort(all(adj[i]));
	dfs(0);
	vis.reset();
	sort(all(subgraph[P]));
	cc = subgraph[P];
	calc(P);
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2208 KB Output is correct
2 Correct 10 ms 2180 KB Output is correct
3 Correct 17 ms 2316 KB Output is correct
4 Correct 4 ms 2180 KB Output is correct
5 Correct 6 ms 2308 KB Output is correct
6 Correct 10 ms 2548 KB Output is correct
7 Correct 20 ms 2444 KB Output is correct
8 Correct 10 ms 2652 KB Output is correct
9 Correct 14 ms 2520 KB Output is correct
10 Correct 8 ms 2180 KB Output is correct
11 Correct 11 ms 2820 KB Output is correct
12 Correct 2 ms 2212 KB Output is correct
13 Correct 20 ms 2444 KB Output is correct
14 Correct 18 ms 2516 KB Output is correct
15 Correct 22 ms 2504 KB Output is correct
16 Correct 19 ms 2316 KB Output is correct
17 Correct 18 ms 2508 KB Output is correct
18 Correct 17 ms 2444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 12592 KB Output is correct
2 Correct 740 ms 12372 KB Output is correct
3 Correct 749 ms 12500 KB Output is correct
4 Correct 726 ms 9640 KB Output is correct
5 Correct 671 ms 11608 KB Output is correct
6 Correct 874 ms 10744 KB Output is correct
7 Correct 898 ms 10812 KB Output is correct
8 Correct 854 ms 11080 KB Output is correct
9 Correct 826 ms 10968 KB Output is correct
10 Correct 396 ms 9448 KB Output is correct
11 Correct 359 ms 9520 KB Output is correct
12 Correct 586 ms 9060 KB Output is correct
13 Correct 604 ms 8976 KB Output is correct
14 Correct 617 ms 9460 KB Output is correct
15 Correct 627 ms 9680 KB Output is correct
16 Correct 637 ms 9788 KB Output is correct
17 Correct 727 ms 9856 KB Output is correct
18 Correct 728 ms 9676 KB Output is correct
19 Correct 739 ms 9756 KB Output is correct
20 Correct 441 ms 11340 KB Output is correct
21 Correct 414 ms 11180 KB Output is correct
22 Correct 886 ms 10344 KB Output is correct
23 Correct 851 ms 11168 KB Output is correct
24 Correct 839 ms 10480 KB Output is correct
25 Correct 852 ms 10748 KB Output is correct
26 Correct 851 ms 10848 KB Output is correct
27 Correct 835 ms 11048 KB Output is correct
28 Correct 848 ms 11100 KB Output is correct
29 Correct 765 ms 10140 KB Output is correct
30 Correct 822 ms 10392 KB Output is correct
31 Correct 8 ms 2436 KB Output is correct
32 Correct 8 ms 2556 KB Output is correct
33 Correct 10 ms 2316 KB Output is correct
34 Correct 7 ms 2180 KB Output is correct
35 Correct 4 ms 2180 KB Output is correct
36 Correct 2 ms 2180 KB Output is correct
37 Correct 2 ms 2328 KB Output is correct
38 Correct 2 ms 2320 KB Output is correct
39 Correct 2 ms 2180 KB Output is correct
40 Correct 4 ms 2180 KB Output is correct
41 Correct 4 ms 2436 KB Output is correct
42 Correct 2 ms 2180 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2316 KB Output is correct
2 Correct 2 ms 2436 KB Output is correct
3 Correct 2 ms 2308 KB Output is correct
4 Correct 72 ms 3996 KB Output is correct
5 Correct 62 ms 4056 KB Output is correct
6 Correct 60 ms 3988 KB Output is correct
7 Correct 60 ms 4060 KB Output is correct
8 Correct 61 ms 4052 KB Output is correct
9 Correct 372 ms 13236 KB Output is correct
10 Correct 376 ms 13220 KB Output is correct
11 Correct 369 ms 13040 KB Output is correct
12 Correct 2 ms 2332 KB Output is correct
13 Correct 3 ms 2180 KB Output is correct
14 Correct 2 ms 2180 KB Output is correct
15 Correct 2 ms 2204 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 12380 KB Output is correct
2 Correct 774 ms 12660 KB Output is correct
3 Correct 761 ms 12296 KB Output is correct
4 Correct 709 ms 9644 KB Output is correct
5 Correct 673 ms 12276 KB Output is correct
6 Correct 825 ms 10852 KB Output is correct
7 Correct 868 ms 10996 KB Output is correct
8 Correct 874 ms 10336 KB Output is correct
9 Correct 876 ms 10516 KB Output is correct
10 Correct 358 ms 9408 KB Output is correct
11 Correct 369 ms 9720 KB Output is correct
12 Correct 609 ms 8932 KB Output is correct
13 Correct 604 ms 8928 KB Output is correct
14 Correct 623 ms 9240 KB Output is correct
15 Correct 638 ms 9672 KB Output is correct
16 Correct 614 ms 9924 KB Output is correct
17 Correct 760 ms 9532 KB Output is correct
18 Correct 722 ms 9804 KB Output is correct
19 Correct 733 ms 9744 KB Output is correct
20 Correct 417 ms 11364 KB Output is correct
21 Correct 432 ms 11068 KB Output is correct
22 Correct 851 ms 10832 KB Output is correct
23 Correct 840 ms 11064 KB Output is correct
24 Correct 848 ms 10888 KB Output is correct
25 Correct 845 ms 11268 KB Output is correct
26 Correct 844 ms 11160 KB Output is correct
27 Correct 848 ms 11168 KB Output is correct
28 Correct 847 ms 10488 KB Output is correct
29 Correct 769 ms 9916 KB Output is correct
30 Correct 809 ms 10484 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 12544 KB Output is correct
2 Correct 759 ms 12464 KB Output is correct
3 Correct 742 ms 12348 KB Output is correct
4 Correct 726 ms 9644 KB Output is correct
5 Correct 681 ms 12724 KB Output is correct
6 Correct 865 ms 10660 KB Output is correct
7 Correct 852 ms 10408 KB Output is correct
8 Correct 813 ms 11192 KB Output is correct
9 Correct 868 ms 11012 KB Output is correct
10 Correct 368 ms 9760 KB Output is correct
11 Correct 395 ms 9348 KB Output is correct
12 Correct 588 ms 8928 KB Output is correct
13 Correct 625 ms 9104 KB Output is correct
14 Correct 628 ms 9488 KB Output is correct
15 Correct 725 ms 9840 KB Output is correct
16 Correct 640 ms 9680 KB Output is correct
17 Correct 711 ms 9752 KB Output is correct
18 Correct 725 ms 9768 KB Output is correct
19 Correct 755 ms 9812 KB Output is correct
20 Correct 426 ms 11200 KB Output is correct
21 Correct 471 ms 11176 KB Output is correct
22 Correct 875 ms 10744 KB Output is correct
23 Correct 850 ms 10652 KB Output is correct
24 Correct 852 ms 10924 KB Output is correct
25 Correct 838 ms 10744 KB Output is correct
26 Correct 836 ms 10508 KB Output is correct
27 Correct 846 ms 11408 KB Output is correct
28 Correct 859 ms 11148 KB Output is correct
29 Correct 806 ms 10824 KB Output is correct
30 Correct 804 ms 10432 KB Output is correct
31 Correct 8 ms 2572 KB Output is correct
32 Correct 10 ms 2564 KB Output is correct
33 Correct 9 ms 2536 KB Output is correct
34 Correct 8 ms 2320 KB Output is correct
35 Correct 4 ms 2560 KB Output is correct
36 Correct 3 ms 2324 KB Output is correct
37 Correct 2 ms 2180 KB Output is correct
38 Correct 2 ms 2180 KB Output is correct
39 Correct 2 ms 2340 KB Output is correct
40 Correct 4 ms 2328 KB Output is correct
41 Correct 4 ms 2180 KB Output is correct
42 Correct 2 ms 2180 KB Output is correct