oj.uz

Submission #1021377

# Submission time Handle Problem Language Result Execution time Memory
1021377 2024-07-12T17:23:46 Z Nika533 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 270 ms 60808 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; 
                    if (!used[u]) q.push(ml[u]);
               }
               v=parent[v];
          }
          ans[cur_ind]=cur_ans; cur_ind++;
     }
}

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 dfs0(long long int, long long int)':
designated_cities.cpp:53:21: warning: unused variable 'w1' [-Wunused-variable]
   53 |           int y=A.f,w1=A.s.f,w2=A.s.s;
      |                     ^~
designated_cities.cpp: At global scope:
designated_cities.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main () {
      | ^~~~

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 184 ms 33876 KB Output is correct
3 Correct 267 ms 60808 KB Output is correct
4 Correct 180 ms 31624 KB Output is correct
5 Correct 168 ms 34584 KB Output is correct
6 Correct 182 ms 37012 KB Output is correct
7 Correct 149 ms 35064 KB Output is correct
8 Correct 270 ms 59580 KB Output is correct
9 Correct 123 ms 37492 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 203 ms 33880 KB Output is correct
3 Correct 263 ms 60804 KB Output is correct
4 Correct 160 ms 31620 KB Output is correct
5 Correct 171 ms 34552 KB Output is correct
6 Correct 195 ms 37832 KB Output is correct
7 Correct 124 ms 37324 KB Output is correct
8 Correct 231 ms 51176 KB Output is correct
9 Correct 126 ms 37376 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 184 ms 33876 KB Output is correct
3 Correct 267 ms 60808 KB Output is correct
4 Correct 180 ms 31624 KB Output is correct
5 Correct 168 ms 34584 KB Output is correct
6 Correct 182 ms 37012 KB Output is correct
7 Correct 149 ms 35064 KB Output is correct
8 Correct 270 ms 59580 KB Output is correct
9 Correct 123 ms 37492 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 203 ms 33880 KB Output is correct
12 Correct 263 ms 60804 KB Output is correct
13 Correct 160 ms 31620 KB Output is correct
14 Correct 171 ms 34552 KB Output is correct
15 Correct 195 ms 37832 KB Output is correct
16 Correct 124 ms 37324 KB Output is correct
17 Correct 231 ms 51176 KB Output is correct
18 Correct 126 ms 37376 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Incorrect 170 ms 33732 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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