Submission #122012

#	Time	Username	Problem	Language	Result	Execution time	Memory
122012		egorlifar	Amusement Park (JOI17_amusement_park)	C++17	98 / 100	31 ms	4944 KiB

Joi

#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> g1[MAXN];
bool used1[MAXN];
int it1 = 0;
long long x;


void dfs1(int u) {
	used1[u] = true;
	MessageBoard(u, (x & (1LL << (it1 % 60))) != 0);
	it1++;
	for (auto h: g1[u]) {
		if (!used1[h]) {
			dfs1(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++){
    	used1[i] = false;
  	}
  	for (int i = 0; i < M; i++) {
  		g1[A[i]].pb(B[i]);
  		g1[B[i]].pb(A[i]);
  	}
  	dfs1(0);
}

Ioi

#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;
		}
		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;
  	}
  	assert(M >= N - 1);
  	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++;
			was[who[pr[cur]]] = true;
			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 = fk - 1; i >= 0; 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: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 53 / 55
• Subtask 5: 17 / 17