제출 #373754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373754		luciocf	Meetings (JOI19_meetings)	C++14	0 / 100	547 ms	262148 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2010;

int n;

int sz[maxn];
bool mark[maxn];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	sz[u] = 1;

	for (auto v: grafo[u])
	{
		if (v == p || mark[v]) continue;

		dfs(v, u);
		sz[u] += sz[v];
	}
}

int centroid(int u, int p, int S)
{
	for (auto v: grafo[u])
		if (v != p && !mark[v] && sz[v] > S/2)
			return centroid(v, u, S);

	return u;
}

void add_edge(int a, int b)
{
	grafo[a].push_back(b);
	grafo[b].push_back(a);
}

void rem_edge(int a, int b)
{
	for (int i = 0; i < grafo[a].size(); i++)
	{
		int v = grafo[a][i];

		if (v == b)
		{
			swap(grafo[a][i], grafo[a].back());
			grafo[a].pop_back();
			break;
		}
	}

	for (int i = 0; i < grafo[b].size(); i++)
	{
		int v = grafo[b][i];

		if (v == a)
		{
			swap(grafo[b][i], grafo[b].back());
			grafo[b].pop_back();
			break;
		}
	}
}

void Solve(int N)
{
	n = N;

	add_edge(1, 2);

	for (int i = 3; i <= n; i++)
	{
		memset(mark, 0, sizeof mark);

		int at = 1;
		bool ok = 0;

		vector<pii> toadd, torem;

		while (true)
		{
			dfs(at, 0);
			int c = centroid(at, 0, sz[at]);
			mark[c] = 1;

			int go = 0;

			for (auto v: grafo[c])
			{
				if (mark[v]) continue;

				int k = Query(c-1, v-1, i-1)+1;
				if (k == c) continue;

				go = v;

				if (k == i)
				{
					torem.push_back({c, v});
					toadd.push_back({c, i}); toadd.push_back({v, i});
					ok = 1;
					break;
				}
			}

			if (!go)
			{
				if (!ok) add_edge(c, i);
				break;
			}

			at = go;
		}

		for (auto pp: torem)
			rem_edge(pp.ff, pp.ss);
		for (auto pp: toadd)
			add_edge(pp.ff, pp.ss);
	}

	set<pair<int, int>> st;

	for (int i = 1; i <= n; i++)
		for (auto j: grafo[i])
			st.insert({min(i, j), max(i, j)});

	for (auto pp: st)
		Bridge(pp.ff-1, pp.ss-1);
}

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'void rem_edge(int, int)':
meetings.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < grafo[a].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
meetings.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 0; i < grafo[b].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71