oj.uz

Submission #373748

# Submission time Handle Problem Language Result Execution time Memory
373748 2021-03-05T15:20:04 Z luciocf Meetings (JOI19_meetings) C++14
0 / 100
 791 ms 832 KB 
#include <bits/stdc++.h>
#include "meetings.h"

#define ff first
#define ss second

using namespace std;

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_between(int a, int b, int c)
{
	grafo[a].push_back(c);

	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();
		}
	}

	grafo[c].push_back(b);
}

void Solve(int N)
{
	n = N;

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

		int at = 1;

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

			bool found = 0;
			bool keep = 0;

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

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

				if (k == i)
				{
					add_between(c, v, i);
					found = 1;
					break;
				}

				keep = 1;
				at = v;
			}

			if (found) break;

			if (!keep)
			{
				grafo[c].push_back(i);
				break;
			}
		}
	}

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

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 71.0

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