제출 #574528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
574528		errorgorn	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	633 ms	107528 KiB

designated_cities

// 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];

vector<int> ans;

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],
		};
	}
}

multiset<int,greater<int> > s[200005];
void dfs2(int i,int p){
	for (auto [it,id]:al[i]){
		if (it==p) continue;
		dfs2(it,i);
		
		int temp=*s[it].begin();
		s[it].erase(s[it].begin());
		s[it].insert(temp+w[id]);
		
		if (sz(s[i])<sz(s[it])) swap(s[i],s[it]);
		for (auto x:s[it]) s[i].insert(x);
	}
	
	if (s[i].empty()) s[i].insert(0);
}

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));
	
	ans={0,0};
	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 curr=0;
	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 (curr<temp.fi+temp.se){
			curr=temp.fi+temp.se;
			best=x;
		}
	}
	
	curr=dfs(al[best][0].fi,best,al[best][0].se).fi;
	dfs2(best,-1);
	while (!s[best].empty()){
		auto it=s[best].begin();
		curr+=*it;
		s[best].erase(it);
		ans.pub(curr);
	}
	
	int tot=0;
	rep(x,0,2*(n-1)) tot+=w[x];
	
	cin>>q;
	while (q--){
		cin>>a;
		cout<<tot-ans[min(a,sz(ans)-1)]<<endl;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:122: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]
  122 |  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:123: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]
  123 |  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
      |            ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44