Submission #574523

#	Time	Username	Problem	Language	Result	Execution time	Memory
574523		errorgorn	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	448 ms	92052 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];

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 (stderr)

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
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44