oj.uz

Submission #122005

# Submission time Handle Problem Language Result Execution time Memory
122005 2019-06-27T11:00:57 Z egorlifar Amusement Park (JOI17_amusement_park) C++17
10 / 100
 28 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;
  	}
  	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) {
  		assert(cur != 0);
  		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 1628 KB Output is correct
2 Correct 5 ms 1544 KB Output is correct
3 Correct 4 ms 1668 KB Output is correct
4 Correct 5 ms 1544 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Incorrect 6 ms 1408 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4780 KB Output is correct
2 Correct 28 ms 4820 KB Output is correct
3 Correct 28 ms 4820 KB Output is correct
4 Correct 19 ms 3264 KB Output is correct
5 Correct 19 ms 3972 KB Output is correct
6 Correct 9 ms 3648 KB Output is correct
7 Correct 20 ms 3776 KB Output is correct
8 Correct 19 ms 3868 KB Output is correct
9 Incorrect 18 ms 3648 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 4 ms 1408 KB Output is correct
4 Correct 6 ms 2076 KB Output is correct
5 Correct 6 ms 2076 KB Output is correct
6 Correct 17 ms 2076 KB Output is correct
7 Correct 6 ms 2076 KB Output is correct
8 Correct 6 ms 2076 KB Output is correct
9 Correct 16 ms 4552 KB Output is correct
10 Correct 19 ms 4668 KB Output is correct
11 Correct 16 ms 4552 KB Output is correct
12 Correct 17 ms 1408 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct
14 Correct 5 ms 1408 KB Output is correct
15 Correct 5 ms 1432 KB Output is correct

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4828 KB Output is correct
2 Correct 28 ms 4812 KB Output is correct
3 Correct 27 ms 4916 KB Output is correct
4 Correct 17 ms 3264 KB Output is correct
5 Correct 18 ms 4296 KB Output is correct
6 Correct 18 ms 3656 KB Output is correct
7 Correct 19 ms 3520 KB Output is correct
8 Correct 18 ms 3924 KB Output is correct
9 Correct 18 ms 3724 KB Output is correct
10 Correct 16 ms 3264 KB Output is correct
11 Correct 17 ms 3364 KB Output is correct
12 Correct 18 ms 3108 KB Output is correct
13 Correct 16 ms 3228 KB Output is correct
14 Correct 16 ms 3328 KB Output is correct
15 Incorrect 19 ms 3400 KB Wrong Answer [7]
16 Halted 0 ms 0 KB -