oj.uz

Submission #122006

# Submission time Handle Problem Language Result Execution time Memory
122006 2019-06-27T11:09:12 Z egorlifar Amusement Park (JOI17_amusement_park) C++17
10 / 100
 30 ms 4916 KB 
#include "Joi.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <chrono>
 
using namespace std;

template<class T1, class T2> inline int chkmin(T1 &x, const T2 &y) {
    if (x > y) {
        x = y;
        return 1;
    }
    else {
        return 0;
    }
}

template<class T1, class T2> inline int chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
        return 1;
    }
    else {
        return 0;
    }
}

#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define mp make_pair
#define pb push_back
const int MAXN = 10228;


vector<int> g[MAXN];
bool used[MAXN];
int it = 0;
long long x;


void dfs(int u) {
	used[u] = true;
	MessageBoard(u, (x & (1LL << (it % 60))) != 0);
	it++;
	for (auto h: g[u]) {
		if (!used[h]) {
			dfs(h);
		}
	}
}


void Joi(int N, int M, int A[], int B[], long long X, int T) {
	assert(T <= 10);
	x = X;
  	for(int i = 0; i < N; i++){
    	used[i] = false;
  	}
  	for (int i = 0; i < M; i++) {
  		g[A[i]].pb(B[i]);
  		g[B[i]].pb(A[i]);
  	}
  	dfs(0);
}

#include "Ioi.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <chrono>
 
using namespace std;

template<class T1, class T2> inline int chkmin(T1 &x, const T2 &y) {
    if (x > y) {
        x = y;
        return 1;
    }
    else {
        return 0;
    }
}

template<class T1, class T2> inline int chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
        return 1;
    }
    else {
        return 0;
    }
}

#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define mp make_pair
#define pb push_back
const int MAXN = 10228;

vector<int> g[MAXN];
bool used[MAXN];
vector<int> v[MAXN];
int pr[MAXN];
int it = 0;
int who[MAXN];
int pos[MAXN];
bool was[MAXN];
long long kek[MAXN];
long long ft;


void dfs(int u) {
	used[u] = true;
	who[u] = it % 60;
	it++;
	kek[u] = 1LL << who[u];
	for (auto h: g[u]) {
		if (!used[h]) {
			pr[h] = u;
			v[u].pb(h);
			pos[h] = sz(v[u]) - 1;
			dfs(h);
			kek[u] |= kek[h];
		}
	}
}

int cnt;
long long res = 0;


bool bfs(int u) {
	for (auto h: v[u]) {
		if ((ft & kek[h]) == kek[h]) continue;
		int gg = Move(h);
		ft |= 1LL << who[h];
		if (!was[who[h]]) {
			cnt++;
			was[who[h]] = true;
			res += (1LL << who[h]) * gg;
		}	
		if (cnt == 60) {
			return true;
		} else {
			if (bfs(h)) {
				return true;
			}
			Move(u);
		}
	}
	return false;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	assert(T <= 10);
  	for (int i = 0; i < N; i++){
    	used[i] = false;
  	}
  	for (int i = 0; i < M; i++) {
  		g[A[i]].pb(B[i]);
  		g[B[i]].pb(A[i]);
  	}
  	for (int i = 0; i < 60; i++) {
  		was[i] = false;
  	}
  	pr[0] = -1;
  	dfs(0);
  	int cur = P;
  	was[who[cur]] = true;
  	res += (1LL << who[cur]) * V;
  	ft |= 1LL << who[cur];
  	cnt = 1;
  	if (bfs(cur)) {
  		return res;
  	}
  	while (true) {
  		int fk = pos[cur];
  		int gg = Move(pr[cur]);
  		ft |= 1LL << who[pr[cur]];
		if (!was[who[pr[cur]]]) {
			cnt++;
			res += (1LL << who[pr[cur]]) * gg;
		}	
		cur = pr[cur];
		if (cnt == 60) {
			return res;
		}
		for (int i = fk + 1; i < sz(v[cur]); i++) {
			int h = v[cur][i];
			if ((ft & kek[h]) == kek[h]) {
				continue;
			}
			int gg = Move(h);
			ft |= 1LL << who[h];
			if (!was[who[h]]) {
				cnt++;
				was[who[h]] = true;
				res += (1LL << who[h]) * gg;
			}
			if (cnt == 60) {
				return res;
			}	
			if (bfs(h)) {
				return res;
			}
			Move(cur);
		}
		for (int i = 0; i < fk; i++) {
			int h = v[cur][i];
			if ((ft & kek[h]) == kek[h]) {
				continue;
			}
			int gg = Move(h);
			ft |= 1LL << who[h];
			if (!was[who[h]]) {
				cnt++;
				was[who[h]] = true;
				res += (1LL << who[h]) * gg;
			}
			if (cnt == 60) {
				return res;
			}	
			if (bfs(h)) {
				return res;
			}
			Move(cur);
		}
  	}
  	return 0LL;	
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1544 KB Output is correct
2 Correct 5 ms 1544 KB Output is correct
3 Correct 4 ms 1668 KB Output is correct
4 Correct 4 ms 1768 KB Output is correct
5 Correct 4 ms 1536 KB Output is correct
6 Incorrect 5 ms 1544 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4692 KB Output is correct
2 Correct 28 ms 4916 KB Output is correct
3 Correct 28 ms 4776 KB Output is correct
4 Correct 18 ms 3272 KB Output is correct
5 Correct 18 ms 3976 KB Output is correct
6 Correct 18 ms 3844 KB Output is correct
7 Correct 18 ms 3648 KB Output is correct
8 Correct 19 ms 3632 KB Output is correct
9 Incorrect 18 ms 3792 KB Wrong Answer [7]
10 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1536 KB Output is correct
2 Correct 5 ms 1544 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 20 ms 1956 KB Output is correct
5 Correct 6 ms 2156 KB Output is correct
6 Correct 7 ms 1956 KB Output is correct
7 Correct 6 ms 2028 KB Output is correct
8 Correct 6 ms 1956 KB Output is correct
9 Correct 16 ms 4424 KB Output is correct
10 Correct 15 ms 4424 KB Output is correct
11 Correct 16 ms 4564 KB Output is correct
12 Correct 4 ms 1644 KB Output is correct
13 Correct 5 ms 1640 KB Output is correct
14 Correct 4 ms 1672 KB Output is correct
15 Correct 5 ms 1648 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4800 KB Output is correct
2 Incorrect 27 ms 4820 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4700 KB Output is correct
2 Correct 27 ms 4684 KB Output is correct
3 Correct 27 ms 4828 KB Output is correct
4 Correct 18 ms 3520 KB Output is correct
5 Correct 18 ms 4364 KB Output is correct
6 Correct 18 ms 3656 KB Output is correct
7 Correct 19 ms 3648 KB Output is correct
8 Correct 19 ms 3784 KB Output is correct
9 Correct 18 ms 3648 KB Output is correct
10 Correct 17 ms 3272 KB Output is correct
11 Correct 16 ms 3272 KB Output is correct
12 Correct 16 ms 3128 KB Output is correct
13 Correct 16 ms 3128 KB Output is correct
14 Correct 16 ms 3236 KB Output is correct
15 Incorrect 18 ms 3440 KB Wrong Answer [7]
16 Halted 0 ms 0 KB -