QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#328499#8038. Hammer to FallPetroTarnavskyi#WA 6ms30196kbC++202.2kb2024-02-15 20:33:052024-02-15 20:33:06

Judging History

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

  • [2024-02-15 20:33:06]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:30196kb
  • [2024-02-15 20:33:05]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1 << 18;

VI g[N];
int rson[N];
VI vecs[N];
multiset<int> s[N][2];
int cost[N][2];
int comp[N];

void dfs(int v)
{
	if (SZ(g[v]) == 1)
	{
		rson[v] = v;
		return;
	}
	FOR(i, 0, SZ(g[v]))
	{
		int to = g[v][i];
		dfs(to);
		if (i < SZ(g[v]) - 1)
		{
			comp[rson[to]] = rson[g[v][0]];
			vecs[rson[g[v][0]]].PB(rson[to]);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	VI a(n), b(n);
	FOR(i, 0, n)
	{
		cin >> a[i] >> b[i];
		cost[i][a[i]] = 0;
		cost[i][a[i] ^ 1] = b[i];
	}
	FOR(i, n, n + m)
	{
		int l;
		cin >> l;
		FOR(j, 0, l)
		{
			int c;
			cin >> c;
			if (c > 0)
				c--;
			else
				c = -c - 1 + n;
			g[i].PB(c);
		}
		sort(ALL(g[i]));
	}
	fill(comp, comp + n, -1);
	dfs(0);
	LL sum0 = 0, sumD = 0;
	FOR(i, 0, n)
	{
		for (int v : vecs[i])
		{
			sum0 += cost[v][0];
			s[i][0].insert(cost[v][1] - cost[v][0]);
		}
		while (SZ(s[i][0]) > SZ(s[i][1]))
		{
			auto it = prev(s[i][0].end());
			s[i][1].insert(*it);
			s[i][0].erase(it);
		}
		for (int x : s[i][0])
			sumD += x;
	}
	while (q--)
	{
		int x, y, z;
		cin >> x >> y >> z;
		x--;
		sum0 -= cost[x][0];
		int i = comp[x];
		int d = cost[x][1] - cost[x][0];
		if (i != -1)
		{
			auto it = s[i][0].find(d);
			if (it != s[i][0].end())
			{
				sumD -= d;
				s[i][0].erase(it);
			}
			else
			{
				it = s[i][1].find(d);
				assert(it != s[i][1].end());
				s[i][1].erase(it);
			}
		}
		cost[x][y] = 0;
		cost[x][y ^ 1] = z;
		sum0 += cost[x][0];
		if (i != -1)
		{
			sumD += d;
			s[i][0].insert(d);
			while (SZ(s[i][0]) > SZ(s[i][1]))
			{
				auto it = prev(s[i][0].end());
				sumD -= *it;
				s[i][1].insert(*it);
				s[i][0].erase(it);
			}
		}
		cout << sum0 + sumD << "\n";
	}
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 30196kb

input:

3 2 2
1 1 1
2 3 10
1 2 1
3 2

output:

0
1

result:

wrong answer 1st lines differ - expected: '12', found: '0'