oj.uz

Submission #574522

# Submission time Handle Problem Language Result Execution time Memory
574522 2022-06-08T17:45:45 Z errorgorn Designated Cities (JOI19_designated_cities) C++17
7 / 100
 470 ms 89488 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;
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],temp2.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 tot=0;
	rep(x,0,2*(n-1)) tot+=w[x];
	cout<<tot-ans[1]<<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
      |            ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 28452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28476 KB Output is correct
2 Correct 406 ms 69724 KB Output is correct
3 Correct 432 ms 88644 KB Output is correct
4 Correct 419 ms 68324 KB Output is correct
5 Correct 421 ms 69616 KB Output is correct
6 Correct 470 ms 72284 KB Output is correct
7 Correct 330 ms 69448 KB Output is correct
8 Correct 432 ms 89488 KB Output is correct
9 Correct 230 ms 68392 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 28452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28476 KB Output is correct
2 Correct 406 ms 69724 KB Output is correct
3 Correct 432 ms 88644 KB Output is correct
4 Correct 419 ms 68324 KB Output is correct
5 Correct 421 ms 69616 KB Output is correct
6 Correct 470 ms 72284 KB Output is correct
7 Correct 330 ms 69448 KB Output is correct
8 Correct 432 ms 89488 KB Output is correct
9 Correct 230 ms 68392 KB Output is correct
10 Incorrect 15 ms 28500 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 28452 KB Output isn't correct
2 Halted 0 ms 0 KB -