Submission #166726

#	Time	Username	Problem	Language	Result	Execution time	Memory
166726		igba	Amusement Park (JOI17_amusement_park)	C++14	82 / 100	51 ms	5384 KiB

Joi

#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());
		for(int j = 0; j < JOIwg[i].size(); ++j)
			MessageBoard(JOIwg[i][j], (X >> j) & 1);
	}
}

Ioi

#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;
}

Compilation message (stderr)

Joi.cpp: In function 'void Joi(int, int, int*, int*, long long int, int)':
Joi.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < JOIwg[i].size(); ++j)
                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 54 / 55
• Subtask 5: 0 / 17