oj.uz

Submission #166725

# Submission time Handle Problem Language Result Execution time Memory
166725 2019-12-03T14:16:11 Z igba Amusement Park (JOI17_amusement_park) C++14
0 / 100
 31 ms 4336 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
vector<int> JOIg[MAXN], JOIwg[MAXN];
bool JOIflg[MAXN];
int JOIgrp[MAXN], JOIgrpsz[MAXN], JOIcurgrp;

void JOIdfs(int v)
{
	JOIflg[v] = true;
	JOIgrp[v] = JOIcurgrp;
	JOIgrpsz[JOIcurgrp]++;
	JOIwg[JOIcurgrp].push_back(v);
	for(const int &u : JOIg[v])
		if(!JOIflg[u])
		{
			if(JOIgrpsz[JOIgrp[v]] == 60)
				JOIcurgrp++;
			JOIdfs(u);
		}
}

void Joi(int N, int M, int A[], int B[], long long X, int T)
{
	for(int i = 0; i < M; ++i)
		JOIg[A[i]].push_back(B[i]), JOIg[B[i]].push_back(A[i]);
	JOIdfs(0);
	
	for(int i = 0; i < N; ++i)
	{
		sort(JOIwg[i].begin(), JOIwg[i].end());
		if(JOIwg[i].size() < 60)
			continue;
		for(int j = 0; j < 60; ++j)
			MessageBoard(JOIwg[i][j], (X >> j) & 1);
	}
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
vector<int> IOIg[MAXN], IOIwg[MAXN];
bool IOIflg[MAXN], IOIsi[MAXN];
int IOIgrp[MAXN], IOIgrpsz[MAXN], IOIcurgrp, IOIparent[MAXN];

void IOIdfs(int v)
{
	IOIflg[v] = true;
	IOIgrp[v] = IOIcurgrp;
	IOIgrpsz[IOIcurgrp]++;
	IOIwg[IOIcurgrp].push_back(v);
	for(const int &u : IOIg[v])
		if(!IOIflg[u])
		{
			if(IOIgrpsz[IOIgrp[v]] == 60)
				IOIcurgrp++;
			IOIparent[u] = v;
			IOIdfs(u);
		}
}

void IOIsolve(int v)
{
	IOIflg[v] = true;
	for(const int &u : IOIg[v])
		if(!IOIflg[u])
		{
			if(IOIgrp[u] != IOIgrp[v])
				continue;
			IOIsi[u] = Move(u);
			IOIsolve(u);
			Move(v);
		}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	for(int i = 0; i < M; ++i)
		IOIg[A[i]].push_back(B[i]), IOIg[B[i]].push_back(A[i]);
	IOIdfs(0);
	for(int i = 0; i < N; ++i)
		sort(IOIwg[i].begin(), IOIwg[i].end());
	IOIsi[P] = V;
	while(IOIgrpsz[IOIgrp[P]] < 60)
	{
		IOIsi[IOIparent[P]] = Move(IOIparent[P]);
		P = IOIparent[P];
	}
	memset(IOIflg, 0, sizeof IOIflg);
	IOIsolve(P);

	long long ans = 0;
	for(int i = 0; i < 60; ++i)
	{
		ans |= (1LL << i) * IOIsi[IOIwg[IOIgrp[P]][i]];
	}
	//printf("ANS: %lld\n", ans);
	return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1788 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4336 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1788 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4336 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 4336 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -