oj.uz

답안 #122001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122001 2019-06-27T10:56:09 Z egorlifar Amusement Park (JOI17_amusement_park) C++17
0 / 100
 41 ms 4268 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;
  	}
  	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1544 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 4236 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1544 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 4268 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 4236 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -