Submission #524578

#	Time	Username	Problem	Language	Result	Execution time	Memory
524578		Killer2501	Designated Cities (JOI19_designated_cities)	C++14	13 / 100	278 ms	43248 KiB

designated_cities

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, int>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 14;
const ll inf = 1e17;
const int base = 350;
const ll mod = 998244353;
int n, t, m, k, q, b[N], c[N], deg[N];
ll ans, tong, a[N], d[N];
vector<int> gr[N], ask[N];
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
string s;
struct BIT
{
    int n;
    vector<int> fe;
    BIT(int _n)
    {
        n = _n;
        fe.resize(n+1, 0);
    }
    void add(int id, int x)
    {
        for(; id <= n; id += id & -id)fe[id] += x;
    }
    int get(int id)
    {
        int total = 0;
        for(; id; id -= id & -id)total += fe[id];
        return total;
    }
};
struct node
{
    int v, c, d;
    node(){}
    node(int _v, int _c, int _d)
    {
        v = _v;
        c = _c;
        d = _d;
    }
};
vector<node> vi, adj[N];
void dfs(int u, int p = 0)
{
    for(node x: adj[u])
    {
        if(x.v == p)continue;
        dfs(x.v, u);
        d[u] += d[x.v] + x.c;
    }
}
void dfs1(int u, ll sum, int p = 0)
{
    sum += d[u];
    a[1] = min(a[1], sum);
    for(node x: adj[u])
    {
        if(x.v == p)continue;
        dfs1(x.v, sum-d[x.v]-x.c+x.d, u);
    }
}
void sol()
{
    cin >> n;
    for(int i = 1; i < n; i ++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        adj[a].pb(node(b, c, d));
        adj[b].pb(node(a, d, c));
        ++deg[a];
        ++deg[b];
    }
    a[1] = inf;
    dfs(1);
    dfs1(1, 0);
    priority_queue< pll, vector<pll>, greater<pll> > pq;
    for(int i = 1; i <= n; i ++)
    {
        if(deg[i] == 1)
        {
            pq.push({adj[i][0].d, i});
        }
    }
    while(pq.size() > 2)
    {
        pii u = pq.top();
        pq.pop();
        int cnt = 0;
        node par = node(-1, 0, 0);
        //cout << u.se <<" "<<u.fi<<'\n';
        for(node x: adj[u.se])
        {

            if(deg[x.v] > 0)
            {
                --deg[x.v];
                --deg[u.se];
                ++cnt;
                if(deg[x.v] == 1)par = x;
                else
                {
                    //cout <<"res "<< pq.size() <<" "<<a[pq.size()+1]+u.fi<<'\n';
                    a[pq.size()] = a[pq.size()+1]+u.fi;
                }
            }
        }
        //assert(cnt <= 1);
        //cout << "par " << par.v<<" "<<par.d << '\n';
        if(par.v != -1)
            for(node x: adj[par.v])
                if(deg[x.v] > 0)
                    pq.push({u.fi+x.d, par.v});
    }
    cin >> m;
    while(m -- > 0)
    {
        cin >> k;
        cout << a[k] << '\n';
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
    return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:140:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:141:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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