oj.uz

Submission #122002

# Submission time Handle Problem Language Result Execution time Memory
122002 2019-06-27T10:57:55 Z egorlifar Amusement Park (JOI17_amusement_park) C++17
10 / 100
 36 ms 5160 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) {
  		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 5 ms 1536 KB Output is correct
2 Correct 4 ms 1544 KB Output is correct
3 Correct 4 ms 1544 KB Output is correct
4 Correct 4 ms 1640 KB Output is correct
5 Correct 4 ms 1676 KB Output is correct
6 Incorrect 6 ms 1540 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 4692 KB Output is correct
2 Correct 28 ms 5140 KB Output is correct
3 Correct 28 ms 5012 KB Output is correct
4 Correct 18 ms 3552 KB Output is correct
5 Correct 19 ms 4016 KB Output is correct
6 Correct 20 ms 3976 KB Output is correct
7 Correct 18 ms 4108 KB Output is correct
8 Correct 19 ms 4016 KB Output is correct
9 Incorrect 17 ms 4024 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 4 ms 1536 KB Output is correct
3 Correct 4 ms 1544 KB Output is correct
4 Correct 7 ms 2156 KB Output is correct
5 Correct 6 ms 2032 KB Output is correct
6 Correct 6 ms 2084 KB Output is correct
7 Correct 6 ms 2180 KB Output is correct
8 Correct 6 ms 1964 KB Output is correct
9 Correct 16 ms 4640 KB Output is correct
10 Correct 15 ms 4704 KB Output is correct
11 Correct 15 ms 4768 KB Output is correct
12 Correct 4 ms 1672 KB Output is correct
13 Correct 5 ms 1672 KB Output is correct
14 Correct 4 ms 1544 KB Output is correct
15 Correct 4 ms 1544 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 28 ms 5160 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 4812 KB Output is correct
2 Correct 36 ms 5132 KB Output is correct
3 Correct 30 ms 5004 KB Output is correct
4 Correct 19 ms 3484 KB Output is correct
5 Correct 19 ms 4528 KB Output is correct
6 Correct 19 ms 4024 KB Output is correct
7 Correct 19 ms 3760 KB Output is correct
8 Correct 19 ms 3888 KB Output is correct
9 Correct 19 ms 3896 KB Output is correct
10 Correct 18 ms 3508 KB Output is correct
11 Correct 16 ms 3516 KB Output is correct
12 Correct 16 ms 3352 KB Output is correct
13 Correct 16 ms 3352 KB Output is correct
14 Correct 18 ms 3372 KB Output is correct
15 Incorrect 18 ms 3632 KB Wrong Answer [7]
16 Halted 0 ms 0 KB -