QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#328499 | #8038. Hammer to Fall | PetroTarnavskyi# | WA | 6ms | 30196kb | C++20 | 2.2kb | 2024-02-15 20:33:05 | 2024-02-15 20:33:06 |
Judging History
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'