oj.uz

Submission #574523

# Submission time Handle Problem Language Result Execution time Memory
574523 2022-06-08T17:52:25 Z errorgorn Designated Cities (JOI19_designated_cities) C++17
16 / 100
 448 ms 92052 KB 
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,q;
vector<ii> al[200005];
int w[400005];

int ans[200005];

ii memo[400005];

ii pp[200005];
vector<ii> childs[200005];
int val[200005];
vector<int> f[200005];
vector<int> b[200005];

ii dfs(int i,int p,int id){
	if (memo[id]!=ii(-1,-1)) return memo[id];
	
	if (pp[i].fi==-1){
		for (auto [it,id]:al[i]){
			if (it==p){
				pp[i]={it,id};
				continue;
			}
			childs[i].pub({it,id});
		}
		
		sort(all(childs[i]));
		f[i].pub(0);
		
		for (auto [it,id]:childs[i]){
			auto temp=dfs(it,i,id);
			val[i]+=temp.fi;
			f[i].pub(temp.se);
		}
		
		b[i].pub(0);
		rep(x,sz(f[i]),1) b[i].pub(f[i][x]);
		reverse(all(b[i]));
		
		rep(x,1,sz(f[i])) f[i][x]=max(f[i][x],f[i][x-1]);
		rep(x,sz(b[i])-1,0) b[i][x]=max(b[i][x],b[i][x+1]);
		
		return memo[id]={val[i]+w[id^1],f[i].back()+w[id]};
	}
	else{
		auto temp1=dfs(pp[i].fi,i,pp[i].se);
		auto temp2=dfs(p,i,id^1);
		int idx=lb(all(childs[i]),ii(p,-1))-childs[i].begin();
		
		return memo[id]={
			val[i]-temp2.fi+temp1.fi+w[id^1],
			max({f[i][idx],b[i][idx+1],temp1.se})+w[id],
		};
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	
	int a,b;
	rep(x,0,n-1){
		cin>>a>>b;
		al[a].pub({b,x<<1});
		al[b].pub({a,x<<1|1});
		cin>>w[x<<1]>>w[x<<1|1];
	}
	
	memset(memo,-1,sizeof(memo));
	memset(pp,-1,sizeof(pp));
	
	rep(x,1,n+1){
		int tot=0;
		for (auto [it,id]:al[x]) tot+=dfs(it,x,id).fi;
		ans[1]=max(ans[1],tot);
	}
	
	int best=-1;
	rep(x,1,n+1) if (sz(al[x])==1){
		auto temp=dfs(al[x][0].fi,x,al[x][0].se);
		if (ans[2]<temp.fi+temp.se){
			ans[2]=temp.fi+temp.se;
			best=x;
		}
	}
	
	int tot=0;
	rep(x,0,2*(n-1)) tot+=w[x];
	
	cin>>q;
	while (q--){
		cin>>a;
		cout<<tot-ans[a]<<endl;
	}
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:105:29: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
  105 |  memset(memo,-1,sizeof(memo));
      |                             ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from designated_cities.cpp:8:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
designated_cities.cpp:106:25: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
  106 |  memset(pp,-1,sizeof(pp));
      |                         ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from designated_cities.cpp:8:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
designated_cities.cpp:114:6: warning: variable 'best' set but not used [-Wunused-but-set-variable]
  114 |  int best=-1;
      |      ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28468 KB Output is correct
2 Incorrect 17 ms 28500 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 15 ms 28520 KB Output is correct
2 Correct 416 ms 63640 KB Output is correct
3 Correct 401 ms 82580 KB Output is correct
4 Correct 392 ms 63576 KB Output is correct
5 Correct 388 ms 63616 KB Output is correct
6 Correct 425 ms 66340 KB Output is correct
7 Correct 334 ms 63280 KB Output is correct
8 Correct 432 ms 83344 KB Output is correct
9 Correct 248 ms 62324 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28448 KB Output is correct
2 Correct 434 ms 69704 KB Output is correct
3 Correct 400 ms 92052 KB Output is correct
4 Correct 424 ms 68212 KB Output is correct
5 Correct 413 ms 69696 KB Output is correct
6 Correct 425 ms 72928 KB Output is correct
7 Correct 279 ms 69804 KB Output is correct
8 Correct 448 ms 81932 KB Output is correct
9 Correct 251 ms 67912 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28520 KB Output is correct
2 Correct 416 ms 63640 KB Output is correct
3 Correct 401 ms 82580 KB Output is correct
4 Correct 392 ms 63576 KB Output is correct
5 Correct 388 ms 63616 KB Output is correct
6 Correct 425 ms 66340 KB Output is correct
7 Correct 334 ms 63280 KB Output is correct
8 Correct 432 ms 83344 KB Output is correct
9 Correct 248 ms 62324 KB Output is correct
10 Correct 15 ms 28448 KB Output is correct
11 Correct 434 ms 69704 KB Output is correct
12 Correct 400 ms 92052 KB Output is correct
13 Correct 424 ms 68212 KB Output is correct
14 Correct 413 ms 69696 KB Output is correct
15 Correct 425 ms 72928 KB Output is correct
16 Correct 279 ms 69804 KB Output is correct
17 Correct 448 ms 81932 KB Output is correct
18 Correct 251 ms 67912 KB Output is correct
19 Correct 15 ms 28452 KB Output is correct
20 Incorrect 436 ms 69772 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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