oj.uz

Submission #1021383

# Submission time Handle Problem Language Result Execution time Memory
1021383 2024-07-12T17:26:08 Z Nika533 Designated Cities (JOI19_designated_cities) C++14
16 / 100
 398 ms 58244 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]=min(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; dfs(r1,0,val[r1]); int r2=mx.s;

     ans[1]=1e18;
     for (int i=1; i<=n; i++) ans[1]=min(ans[1],tot-val[i]);
     for (int i=2; i<=n; i++) ans[i]=1e18;

     solve(r1); solve(r2);

     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:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main () {
      | ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Incorrect 2 ms 4952 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 2 ms 5116 KB Output is correct
2 Correct 247 ms 29312 KB Output is correct
3 Correct 398 ms 58244 KB Output is correct
4 Correct 259 ms 27688 KB Output is correct
5 Correct 229 ms 29264 KB Output is correct
6 Correct 282 ms 32612 KB Output is correct
7 Correct 199 ms 28824 KB Output is correct
8 Correct 384 ms 57108 KB Output is correct
9 Correct 155 ms 31136 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 240 ms 29364 KB Output is correct
3 Correct 398 ms 58220 KB Output is correct
4 Correct 231 ms 27508 KB Output is correct
5 Correct 240 ms 29308 KB Output is correct
6 Correct 275 ms 33496 KB Output is correct
7 Correct 162 ms 30964 KB Output is correct
8 Correct 340 ms 48856 KB Output is correct
9 Correct 153 ms 31028 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5116 KB Output is correct
2 Correct 247 ms 29312 KB Output is correct
3 Correct 398 ms 58244 KB Output is correct
4 Correct 259 ms 27688 KB Output is correct
5 Correct 229 ms 29264 KB Output is correct
6 Correct 282 ms 32612 KB Output is correct
7 Correct 199 ms 28824 KB Output is correct
8 Correct 384 ms 57108 KB Output is correct
9 Correct 155 ms 31136 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 240 ms 29364 KB Output is correct
12 Correct 398 ms 58220 KB Output is correct
13 Correct 231 ms 27508 KB Output is correct
14 Correct 240 ms 29308 KB Output is correct
15 Correct 275 ms 33496 KB Output is correct
16 Correct 162 ms 30964 KB Output is correct
17 Correct 340 ms 48856 KB Output is correct
18 Correct 153 ms 31028 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Incorrect 254 ms 29436 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 4952 KB Output is correct
2 Incorrect 2 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -