oj.uz

Submission #1021407

# Submission time Handle Problem Language Result Execution time Memory
1021407 2024-07-12T17:36:52 Z Nika533 Designated Cities (JOI19_designated_cities) C++14
100 / 100
 440 ms 53328 KB 
#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;

const int N=2e5+5;
int n,m,T,k,q,tot,sum,val[N],ans[N];
pii mx={0,0};
vector<pair<int,pii>> g[N];

pii ml[N];
int parent[N];

void dfs_build(int x, int p) {
     ml[x]={0,x}; parent[x]=p;
     for (auto A:g[x]) {
          int y=A.f,w1=A.s.f,w2=A.s.s;
          if (y==p) continue;
          dfs_build(y,x); ml[x]=max(ml[x],{ml[y].f+w1,ml[y].s});
     }
}

void solve(int root) {
     dfs_build(root,0);
     vector<bool> used(n+1,0); used[0]=1;
     priority_queue<pii> q; q.push(ml[root]);
     int cur_ans=tot-val[root],cur_ind=2;
     while (!q.empty()) {
          pii AA=q.top(); q.pop();
          int v=AA.s,num=AA.f;
          cur_ans-=num;
          while (!used[v]) {
               used[v]=1;
               for (auto A:g[v]) {
                    int u=A.f,w1=A.s.f,w2=A.s.s; 
                    if (u!=parent[v] && !used[u]) q.push({ml[u].f+w1,ml[u].s});
               }
               v=parent[v];
          }
          ans[cur_ind]=cur_ans; cur_ind++;
     }
     for (int i=cur_ind; i<=n; i++) ans[i]=0;
}

void dfs0(int x, int p) {
     for (auto A:g[x]) {
          int y=A.f,w1=A.s.f,w2=A.s.s;
          if (y==p) continue;
          sum+=w2; dfs0(y,x);
     }
}
void dfs1(int x, int p) {
     val[x]=sum; 
     for (auto A:g[x]) {
          int y=A.f,w1=A.s.f,w2=A.s.s;
          if (y==p) continue;
          sum+=w1-w2; dfs1(y,x); sum-=w1-w2; 
     }
}
void dfs(int x, int p, int dist) {
     mx=max(mx,{dist+val[x],x});
     for (auto A:g[x]) {
          int y=A.f,w1=A.s.f,w2=A.s.s;
          if (y==p) continue;
          dfs(y,x,dist+w1+w2);
     }
}

void test_case() {
     cin>>n;
     for (int i=1; i<=n-1; i++) {
          int a,b,c,d; cin>>a>>b>>c>>d;
          g[a].pb({b,{c,d}}); g[b].pb({a,{d,c}});
          tot+=c+d;
     }
     cin>>q;
     int query[q+1];
     for (int i=1; i<=q; i++) cin>>query[i];
 
     dfs0(1,0); dfs1(1,1);
     dfs(1,0,val[1]); int r1=mx.s; 
 
     ans[1]=1e18;
     for (int i=1; i<=n; i++) ans[1]=min(ans[1],tot-val[i]);
 
     solve(r1);
 
     for (int i=1; i<=q; i++) cout<<ans[query[i]]<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1; 
	while (T--) test_case();
}

Compilation message

designated_cities.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
designated_cities.cpp: In function 'void dfs_build(long long int, long long int)':
designated_cities.cpp:24:30: warning: unused variable 'w2' [-Wunused-variable]
   24 |           int y=A.f,w1=A.s.f,w2=A.s.s;
      |                              ^~
designated_cities.cpp: In function 'void solve(long long int)':
designated_cities.cpp:42:40: warning: unused variable 'w2' [-Wunused-variable]
   42 |                     int u=A.f,w1=A.s.f,w2=A.s.s;
      |                                        ^~
designated_cities.cpp: In function 'void dfs0(long long int, long long int)':
designated_cities.cpp:54:21: warning: unused variable 'w1' [-Wunused-variable]
   54 |           int y=A.f,w1=A.s.f,w2=A.s.s;
      |                     ^~
designated_cities.cpp: At global scope:
designated_cities.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main () {
      | ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 5104 KB Output is correct
7 Correct 3 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 5172 KB Output is correct
11 Correct 2 ms 4952 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 168 ms 27080 KB Output is correct
3 Correct 202 ms 51000 KB Output is correct
4 Correct 147 ms 26192 KB Output is correct
5 Correct 152 ms 27860 KB Output is correct
6 Correct 155 ms 30160 KB Output is correct
7 Correct 145 ms 28412 KB Output is correct
8 Correct 258 ms 50136 KB Output is correct
9 Correct 124 ms 30960 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 171 ms 27088 KB Output is correct
3 Correct 205 ms 51024 KB Output is correct
4 Correct 147 ms 26192 KB Output is correct
5 Correct 168 ms 27904 KB Output is correct
6 Correct 180 ms 31180 KB Output is correct
7 Correct 149 ms 30860 KB Output is correct
8 Correct 237 ms 42904 KB Output is correct
9 Correct 122 ms 30960 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 5104 KB Output is correct
7 Correct 3 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 5172 KB Output is correct
11 Correct 2 ms 4952 KB Output is correct
12 Correct 3 ms 4952 KB Output is correct
13 Correct 5 ms 5212 KB Output is correct
14 Correct 5 ms 5468 KB Output is correct
15 Correct 5 ms 5296 KB Output is correct
16 Correct 5 ms 5456 KB Output is correct
17 Correct 5 ms 5208 KB Output is correct
18 Correct 5 ms 5212 KB Output is correct
19 Correct 5 ms 5208 KB Output is correct
20 Correct 5 ms 5212 KB Output is correct
21 Correct 5 ms 5468 KB Output is correct
22 Correct 5 ms 5400 KB Output is correct
23 Correct 5 ms 5208 KB Output is correct
24 Correct 5 ms 5468 KB Output is correct
25 Correct 6 ms 5468 KB Output is correct
26 Correct 5 ms 5468 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 168 ms 27080 KB Output is correct
3 Correct 202 ms 51000 KB Output is correct
4 Correct 147 ms 26192 KB Output is correct
5 Correct 152 ms 27860 KB Output is correct
6 Correct 155 ms 30160 KB Output is correct
7 Correct 145 ms 28412 KB Output is correct
8 Correct 258 ms 50136 KB Output is correct
9 Correct 124 ms 30960 KB Output is correct
10 Correct 2 ms 4952 KB Output is correct
11 Correct 171 ms 27088 KB Output is correct
12 Correct 205 ms 51024 KB Output is correct
13 Correct 147 ms 26192 KB Output is correct
14 Correct 168 ms 27904 KB Output is correct
15 Correct 180 ms 31180 KB Output is correct
16 Correct 149 ms 30860 KB Output is correct
17 Correct 237 ms 42904 KB Output is correct
18 Correct 122 ms 30960 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 159 ms 27120 KB Output is correct
21 Correct 245 ms 51112 KB Output is correct
22 Correct 148 ms 26196 KB Output is correct
23 Correct 157 ms 27344 KB Output is correct
24 Correct 152 ms 27336 KB Output is correct
25 Correct 176 ms 27336 KB Output is correct
26 Correct 176 ms 27328 KB Output is correct
27 Correct 158 ms 27400 KB Output is correct
28 Correct 162 ms 30604 KB Output is correct
29 Correct 167 ms 27600 KB Output is correct
30 Correct 163 ms 27396 KB Output is correct
31 Correct 130 ms 28536 KB Output is correct
32 Correct 199 ms 43792 KB Output is correct
33 Correct 120 ms 30964 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 4 ms 4956 KB Output is correct
6 Correct 3 ms 5104 KB Output is correct
7 Correct 3 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 5172 KB Output is correct
11 Correct 2 ms 4952 KB Output is correct
12 Correct 2 ms 4952 KB Output is correct
13 Correct 168 ms 27080 KB Output is correct
14 Correct 202 ms 51000 KB Output is correct
15 Correct 147 ms 26192 KB Output is correct
16 Correct 152 ms 27860 KB Output is correct
17 Correct 155 ms 30160 KB Output is correct
18 Correct 145 ms 28412 KB Output is correct
19 Correct 258 ms 50136 KB Output is correct
20 Correct 124 ms 30960 KB Output is correct
21 Correct 2 ms 4952 KB Output is correct
22 Correct 171 ms 27088 KB Output is correct
23 Correct 205 ms 51024 KB Output is correct
24 Correct 147 ms 26192 KB Output is correct
25 Correct 168 ms 27904 KB Output is correct
26 Correct 180 ms 31180 KB Output is correct
27 Correct 149 ms 30860 KB Output is correct
28 Correct 237 ms 42904 KB Output is correct
29 Correct 122 ms 30960 KB Output is correct
30 Correct 3 ms 4952 KB Output is correct
31 Correct 5 ms 5212 KB Output is correct
32 Correct 5 ms 5468 KB Output is correct
33 Correct 5 ms 5296 KB Output is correct
34 Correct 5 ms 5456 KB Output is correct
35 Correct 5 ms 5208 KB Output is correct
36 Correct 5 ms 5212 KB Output is correct
37 Correct 5 ms 5208 KB Output is correct
38 Correct 5 ms 5212 KB Output is correct
39 Correct 5 ms 5468 KB Output is correct
40 Correct 5 ms 5400 KB Output is correct
41 Correct 5 ms 5208 KB Output is correct
42 Correct 5 ms 5468 KB Output is correct
43 Correct 6 ms 5468 KB Output is correct
44 Correct 5 ms 5468 KB Output is correct
45 Correct 2 ms 4952 KB Output is correct
46 Correct 159 ms 27120 KB Output is correct
47 Correct 245 ms 51112 KB Output is correct
48 Correct 148 ms 26196 KB Output is correct
49 Correct 157 ms 27344 KB Output is correct
50 Correct 152 ms 27336 KB Output is correct
51 Correct 176 ms 27336 KB Output is correct
52 Correct 176 ms 27328 KB Output is correct
53 Correct 158 ms 27400 KB Output is correct
54 Correct 162 ms 30604 KB Output is correct
55 Correct 167 ms 27600 KB Output is correct
56 Correct 163 ms 27396 KB Output is correct
57 Correct 130 ms 28536 KB Output is correct
58 Correct 199 ms 43792 KB Output is correct
59 Correct 120 ms 30964 KB Output is correct
60 Correct 3 ms 4956 KB Output is correct
61 Correct 365 ms 28964 KB Output is correct
62 Correct 434 ms 53328 KB Output is correct
63 Correct 368 ms 29196 KB Output is correct
64 Correct 388 ms 29488 KB Output is correct
65 Correct 371 ms 29244 KB Output is correct
66 Correct 400 ms 29520 KB Output is correct
67 Correct 382 ms 28996 KB Output is correct
68 Correct 373 ms 29392 KB Output is correct
69 Correct 370 ms 32420 KB Output is correct
70 Correct 418 ms 29920 KB Output is correct
71 Correct 366 ms 29732 KB Output is correct
72 Correct 426 ms 30412 KB Output is correct
73 Correct 440 ms 45460 KB Output is correct
74 Correct 344 ms 32536 KB Output is correct