oj.uz

Submission #524578

# Submission time Handle Problem Language Result Execution time Memory
524578 2022-02-09T14:58:36 Z Killer2501 Designated Cities (JOI19_designated_cities) C++14
13 / 100
 278 ms 43248 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 7 ms 14400 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14328 KB Output is correct
8 Correct 7 ms 14416 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14412 KB Output is correct
11 Correct 9 ms 14416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 278 ms 27168 KB Output is correct
3 Correct 222 ms 42064 KB Output is correct
4 Correct 275 ms 32180 KB Output is correct
5 Correct 260 ms 33864 KB Output is correct
6 Correct 272 ms 35252 KB Output is correct
7 Correct 228 ms 35236 KB Output is correct
8 Correct 244 ms 43248 KB Output is correct
9 Correct 233 ms 37096 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Incorrect 254 ms 27220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 7 ms 14400 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14328 KB Output is correct
8 Correct 7 ms 14416 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14412 KB Output is correct
11 Correct 9 ms 14416 KB Output is correct
12 Correct 7 ms 14404 KB Output is correct
13 Incorrect 9 ms 14668 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 278 ms 27168 KB Output is correct
3 Correct 222 ms 42064 KB Output is correct
4 Correct 275 ms 32180 KB Output is correct
5 Correct 260 ms 33864 KB Output is correct
6 Correct 272 ms 35252 KB Output is correct
7 Correct 228 ms 35236 KB Output is correct
8 Correct 244 ms 43248 KB Output is correct
9 Correct 233 ms 37096 KB Output is correct
10 Correct 8 ms 14412 KB Output is correct
11 Incorrect 254 ms 27220 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 8 ms 14416 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 7 ms 14400 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 8 ms 14328 KB Output is correct
8 Correct 7 ms 14416 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14412 KB Output is correct
11 Correct 9 ms 14416 KB Output is correct
12 Correct 9 ms 14412 KB Output is correct
13 Correct 278 ms 27168 KB Output is correct
14 Correct 222 ms 42064 KB Output is correct
15 Correct 275 ms 32180 KB Output is correct
16 Correct 260 ms 33864 KB Output is correct
17 Correct 272 ms 35252 KB Output is correct
18 Correct 228 ms 35236 KB Output is correct
19 Correct 244 ms 43248 KB Output is correct
20 Correct 233 ms 37096 KB Output is correct
21 Correct 8 ms 14412 KB Output is correct
22 Incorrect 254 ms 27220 KB Output isn't correct
23 Halted 0 ms 0 KB -