QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#624805#6127. Kawa ExamMaxDYFRE 0ms3564kbC++235.4kb2024-10-09 16:39:132024-10-09 16:39:14

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 16:39:14]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3564kb
  • [2024-10-09 16:39:13]
  • 提交

answer


// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

void work()
{
	cin >> n >> m;
	vector<int> a(n + 1), head(n + 1);
	struct Edges
	{
		struct Edge
		{
			int to, nxt, id;
			Edge() {}
			Edge(int t, int n, int i) : to(t), nxt(n), id(i) {}
		};
		vector<int> head;
		vector<Edge> e;
		Edges() {}
		Edges(int n)
		{
			head.resize(n + 1);
			e.clear();
			e.push_back(Edge());
		}
		void addSingle(int x, int y, int id)
		{

			e.push_back(Edge(y, head[x], id));
			head[x] = e.size() - 1;
		}
		void add(int x, int y, int id)
		{
			addSingle(x, y, id);
			addSingle(y, x, id);
		}
	};
	Edges G(n), newG(n);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		if (x != y)
			G.add(x, y, i);
	}
	vector<int> dfn(n + 1), low(n + 1), col(n + 1), stk;
	int dfncnt = 0, scccnt = 0;
	vector<vector<int>> newa(n + 1);
	auto tarjan = [&](auto &tarjan, int x, int fromID) -> void
	{
		stk.push_back(x);
		dfn[x] = low[x] = ++dfncnt;
		for (int i = G.head[x]; i; i = G.e[i].nxt)
		{
			if (G.e[i].id == fromID)
				continue;
			int y = G.e[i].to;
			if (!dfn[y])
			{
				tarjan(tarjan, y, G.e[i].id);
				low[x] = min(low[x], low[y]);
			}
			else
				low[x] = min(low[x], dfn[y]);
		}
		if (dfn[x] == low[x])
		{
			scccnt++;
			int now = 0;
			do
			{
				now = stk.back();
				col[now] = scccnt;
				newa[scccnt].push_back(a[now]);
				stk.pop_back();
			} while (now != x);
		}
	};
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(tarjan, i, 0);
	for (int x = 1; x <= n; x++)
	{
		for (int i = G.head[x]; i; i = G.e[i].nxt)
		{
			int y = G.e[i].to;
			if (col[x] == col[y])
				continue;
			newG.addSingle(col[x], col[y], G.e[i].id);
		}
	}
	vector<int> siz(scccnt + 1), hson(scccnt + 1);
	auto dfs0 = [&](auto &dfs0, int x, int f) -> void
	{
		siz[x] = 1;
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f)
				continue;
			dfs0(dfs0, y, x);
			if (siz[hson[x]] < siz[y])
				hson[x] = y;
			siz[x] += siz[y];
		}
	};
	for (int i = 1; i <= scccnt; i++)
		if (siz[i] == 0)
			dfs0(dfs0, i, 0);
	vector<int> ans(m + 1), vis(scccnt + 1);
	struct State
	{
		unordered_map<int, int> cnt, cntcnt;
		int maxcnt = 0;
		void clear()
		{
			maxcnt = 0;
			cnt.clear();
			cntcnt.clear();
		}
		void addone(int x)
		{
			if (cnt[x])
				cntcnt[cnt[x]]--;
			cnt[x]++;
			cntcnt[cnt[x]]++;
			if (cnt[x] > maxcnt)
				maxcnt = cnt[x];
		}
		void subone(int x)
		{
			cntcnt[cnt[x]]--;
			if (cnt[x] == maxcnt && cntcnt[maxcnt] == 0 && maxcnt != 0)
				maxcnt--;
			cnt[x]--;
			if (cnt[x])
				cntcnt[cnt[x]]++;
		}
	};
	State all;
	vector<int> vis0(n + 1);
	auto addon0 = [&](auto &addon0, int x, int f) -> void
	{
		vis0[x] = 1;
		for (auto v : newa[x])
			all.addone(v);
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
			if (newG.e[i].to != f)
				addon0(addon0, newG.e[i].to, x);
	};
	int sum = 0;
	for (int i = 1; i <= scccnt; i++)
		if (!vis0[i])
		{
			addon0(addon0, i, 0);
			sum += all.maxcnt;
			all.clear();
		}
	for (int i = 1; i <= m; i++)
		ans[i] = sum;
	State up, down;
	auto changeSubtree = [&](auto &changeSubtree, int x, bool increase, int f) -> void
	{
		if (increase)
		{
			for (auto v : newa[x])
			{
				up.subone(v);
				down.addone(v);
			}
		}
		else
		{
			for (auto v : newa[x])
			{
				down.subone(v);
				up.addone(v);
			}
		}
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f)
				continue;
			changeSubtree(changeSubtree, y, increase, x);
		}
	};
	int subtreeAns = 0;
	auto dfs = [&](auto &dfs, int x, int fromID, int f, bool keep) -> void
	{
		int hsonID = -1;
		vis[x] = 1;
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f)
				continue;
			if (y == hson[x])
			{
				hsonID = newG.e[i].id;
				break;
			}
			dfs(dfs, y, newG.e[i].id, x, false);
		}
		if (hson[x])
			dfs(dfs, hson[x], hsonID, x, true);
		for (int i = newG.head[x]; i; i = newG.e[i].nxt)
		{
			int y = newG.e[i].to;
			if (y == f || y == hson[x])
				continue;
			changeSubtree(changeSubtree, y, 1, x);
		}
		for (auto v : newa[x])
		{
			up.subone(v);
			down.addone(v);
		}
		if (fromID)
			ans[fromID] = ans[fromID] - subtreeAns + up.maxcnt + down.maxcnt;
		if (!keep)
			changeSubtree(changeSubtree, x, 0, f);
	};
	for (int i = 1; i <= scccnt; i++)
	{
		if (!vis[i])
		{
			up.clear();
			down.clear();
			auto addon = [&](auto &addon, int x, int f) -> void
			{
				for (auto v : newa[x])
					up.addone(v);
				for (int i = newG.head[x]; i; i = newG.e[i].nxt)
					if (newG.e[i].to != f)
						addon(addon, newG.e[i].to, x);
			};
			addon(addon, i, 0);
			subtreeAns = up.maxcnt;
			dfs(dfs, i, 0, 0, 0);
		}
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << " \n"[i == m];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t-- > 0)
	{
		work();
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3564kb

input:

3
7 5
1 2 1 2 1 2 1
1 2
1 3
2 4
5 6
5 7
3 3
1 2 3
1 2
1 3
2 3
2 3
12345 54321
1 2
1 2
1 1

output:

6 5 5 5 4
1 1 1
1 1 1

result:

ok 3 lines

Test #2:

score: -100
Runtime Error

input:

5557
2 7
79960 79960
2 2
1 1
1 1
2 2
1 1
2 1
1 2
9 8
21881 70740 70740 21881 22458 22458 639 21881 70740
3 3
1 6
5 8
7 5
5 7
2 3
5 1
7 6
6 7
13064 20716 6746 13064 6746 69225
5 5
4 1
4 1
1 6
4 5
3 2
3 2
8 4
45146 14400 45146 45146 14400 72969 14400 45146
8 6
1 3
4 6
8 3
18 13
48132 37949 92338 92338...

output:


result: