Submission #105935

#	Time	Username	Problem	Language	Result	Execution time	Memory
105935		JustasZ	Designated Cities (JOI19_designated_cities)	C++14	0 / 100	774 ms	61164 KiB

designated_cities

#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>pii;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, q, tin[maxn], tout[maxn], tim, vert[maxn], par[maxn];
vector<pii>adj[maxn];
ll up, sum[maxn], ans[maxn], tot;
void dfs(int v, ll csum = 0)
{
    tin[v] = ++tim;
    for(pii to : adj[v])
    {
        if(to.x == par[v])
            up += to.y;
        else
        {
            par[to.x] = v;
            dfs(to.x, csum + to.y);
        }
    }
    tout[v] = tim;
    if(tin[v] == tout[v])
    {
        sum[tin[v]] = csum;
        vert[tin[v]] = v;
    }
}
pii seg[maxn * 4];
ll lazy[maxn * 4];
void build(int id = 1, int l = 1, int r = n)
{
    if(l == r)
    {
        seg[id] = {sum[l], vert[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}
void upd(int id, ll val)
{
    seg[id].x += val;
    lazy[id] += val;
}
void shift(int id)
{
    if(!lazy[id]) return;
    upd(id * 2, lazy[id]);
    upd(id * 2 + 1, lazy[id]);
    lazy[id] = 0;
}
void modify(int x, int y, ll val, int id = 1, int l = 1, int r = n)
{
    if(l > y || r < x) return;
    if(l >= x && r <= y)
    {
        upd(id, val);
        return;
    }
    shift(id);
    int mid = (l + r) / 2;
    modify(x, y, val, id * 2, l, mid);
    modify(x, y, val, id * 2 + 1, mid + 1, r);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}
map<int, int>edge[maxn];
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        ll c, d;
        cin >> a >> b >> c >> d;
        tot += c + d;
        adj[a].pb({b, c});
        adj[b].pb({a, d});
        edge[a][b] = c;
        edge[b][a] = d;
    }
    dfs(1);
    build();
    ll cur_ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(seg[1].x == 0) break;
        pii best = seg[1];
        cur_ans += best.x;
        if(i >= 2)
            ans[i] = tot - (up + cur_ans);
        int v = best.y;
        while(edge[v].count(par[v]))
        {
            modify(tin[v], tout[v], -edge[par[v]][v]);
            edge[v].erase(edge[v].find(par[v]));
            v = par[v];
        }
    }
    assert(seg[1].x == 0);
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        int c; cin >> c;
        cout << ans[c] << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44