QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#167061#6514. Is it well known in Poland?ucup-team134#WA 3ms9108kbC++145.5kb2023-09-07 00:50:322023-09-07 00:50:32

Judging History

你现在查看的是最新测评结果

  • [2023-09-07 00:50:32]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:9108kb
  • [2023-09-07 00:50:32]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<int D, typename T>struct vec : public vector<vec<D - 1, T>> {template<typename... Args>vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}};
template<typename T>struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val) {}};
template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
int ri(){int x;scanf("%i",&x);return x;}
void rd(int&x){scanf("%i",&x);}
void rd(long long&x){scanf("%lld",&x);}
void rd(double&x){scanf("%lf",&x);}
void rd(long double&x){scanf("%Lf",&x);}
void rd(string&x){cin>>x;}
void rd(char*x){scanf("%s",x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);}
template<typename C,typename...T>void rd(C&a,T&...args){rd(a);rd(args...);}
//istream& operator>>(istream& is,__int128& a){string s;is>>s;a=0;int i=0;bool neg=false;if(s[0]=='-')neg=true,i++;for(;i<s.size();i++)a=a*10+s[i]-'0';if(neg)a*=-1;return is;}
//ostream& operator<<(ostream& os,__int128 a){bool neg=false;if(a<0)neg=true,a*=-1;ll high=(a/(__int128)1e18);ll low=(a-(__int128)1e18*high);string res;if(neg)res+='-';if(high>0){res+=to_string(high);string temp=to_string(low);res+=string(18-temp.size(),'0');res+=temp;}else res+=to_string(low);os<<res;return os;}

const int N=1e5+5;
vector<set<pair<ll,int>>> graf(N);
vector<ll> val(N);
vector<int> ord;
vector<int> par(N);
void dfs(int tr,int parent){
	par[tr]=parent;
	for(auto p:graf[tr]){
		if(p.s!=parent){
			dfs(p.s,tr);
		}
	}
	if(graf[tr].count({val[parent],parent})){
		graf[tr].erase({val[parent],parent});
	}
	ord.pb(tr);
}
int main()
{
	int n=ri();
	ll sum=0;
	for(int i=0;i<n;i++){
		val[i]=ri();
		sum+=val[i];
	}
	for(int i=1;i<n;i++){
		int u=ri()-1,v=ri()-1;
		graf[u].insert({val[v],v});
		graf[v].insert({val[u],u});
	}
	dfs(0,0);
	ll ans=0;
	vector<bool> exists(n,1);
	for(auto ind:ord){
		while(1){
			if(sz(graf[ind])==0)
				break;
			if((*graf[ind].rbegin()).f<val[ind])
				break;
			// Worthless move
			if(sz(graf[ind])==1&&sz(graf[(*graf[ind].begin()).s])==0){
				if(n&1){
					ans+=(*graf[ind].rbegin()).f-val[ind];
				}
				else{
					ans+=val[ind]-(*graf[ind].rbegin()).f;
				}
				graf[par[ind]].erase({val[ind],ind});
				exists[ind]=0;
				break;
			}
			
			int koji=(*graf[ind].rbegin()).s,koji2;
			graf[ind].erase({val[koji],koji});
			if(sz(graf[koji])==0||(sz(graf[ind])!=0&&(*graf[koji].rbegin()).f<=(*graf[ind].rbegin()).f)){
				//Taking from root
				koji2=(*graf[ind].rbegin()).s;
				graf[ind].erase({val[koji2],koji2});
			}
			else{
				koji2=(*graf[koji].rbegin()).s;
				graf[koji].erase({val[koji2],koji2});
			}
			/*if(sz(graf[koji])>sz(graf[ind])){
				swap(graf[koji],graf[ind]);
			}
			if(sz(graf[koji2])>sz(graf[ind])){
				swap(graf[koji2],graf[ind]);
			}*/
			for(auto p:graf[koji]){
				graf[ind].insert(p);
			}
			for(auto p:graf[koji2]){
				graf[ind].insert(p);
			}
			if(par[ind]!=ind){
				graf[par[ind]].erase({val[ind],ind});
			}
			val[ind]=val[ind]+val[koji2]-val[koji];
			if(par[ind]!=ind){
				graf[par[ind]].insert({val[ind],ind});
			}
			//cout << ind << ": " << val[ind] << graf[ind] << endl;
		}
	}
	if(exists[0]){
		set<pair<int,int>> options;
		options.insert({val[0],0});
		int v=1;
		while(sz(options)){
			auto tr=*options.rbegin();
			options.erase(tr);
			ans+=tr.f*v;
			v*=-1;
			for(auto p:graf[tr.s]){
				options.insert(p);
			}
		}
	}
	//printf("ans: %lld\n",ans);
	printf("%lld\n",(ans+sum)/2);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 8932kb

input:

5
1 5 3 2 4
1 2
1 3
2 4
2 5

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 1ms
memory: 8924kb

input:

20
530933472 920863930 136179483 46535289 291417568 338674057 731327836 375973098 986104110 203163644 489326483 785212564 712578139 801609721 666347686 282530991 823910542 217884304 785578553 116701831
8 3
18 19
11 20
2 18
8 13
5 15
12 16
7 8
10 9
13 6
17 10
17 18
13 15
18 4
13 12
1 14
17 15
15 14
5...

output:

4611098449

result:

ok 1 number(s): "4611098449"

Test #3:

score: 0
Accepted
time: 1ms
memory: 8904kb

input:

20
384529189 217795442 901954855 742992564 354875060 497288585 40376145 575315239 263212445 574630916 520470316 917128880 461333242 407666839 565926566 390970156 568486150 291329847 493439854 637783217
10 17
19 8
20 17
7 17
9 6
17 14
16 18
4 3
9 14
6 2
14 18
13 4
11 15
9 3
7 12
16 1
8 14
5 14
9 15

output:

4410782058

result:

ok 1 number(s): "4410782058"

Test #4:

score: 0
Accepted
time: 0ms
memory: 8940kb

input:

19
601996737 696498327 385657564 527861058 529330573 376647612 223077352 338754937 682264670 671903443 645156487 755321105 978945836 120368247 611275923 947566064 98892994 858404931 401419272
11 14
8 14
3 6
13 12
16 15
1 4
11 4
2 7
4 3
15 5
2 1
13 5
10 16
9 16
1 17
18 6
3 19
5 7

output:

5848746543

result:

ok 1 number(s): "5848746543"

Test #5:

score: 0
Accepted
time: 0ms
memory: 9108kb

input:

1000
379354617 199235046 102686848 841958378 178689385 896777301 798019293 538540178 877449071 825184825 426375184 882476194 614078703 438824267 731949932 770345838 655572525 687098129 758287148 690715403 984914877 365231609 752380073 509777049 511312331 889780846 745450511 740863321 552773286 15071...

output:

252915929540

result:

ok 1 number(s): "252915929540"

Test #6:

score: 0
Accepted
time: 3ms
memory: 9036kb

input:

999
402468827 468124822 806603931 945584323 480102625 19722 169790452 515757998 19958108 528988204 415841643 111279190 885615782 740479752 550815713 556065700 511850711 148616044 552183365 471481958 946651162 968386282 610171866 971986310 377716133 564442897 222395758 16053401 613716892 487668831 48...

output:

249829986618

result:

ok 1 number(s): "249829986618"

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 9056kb

input:

1000
637313417 62510663 83128345 702987667 374713776 778401168 619811617 896369345 486498325 448824176 297332011 916674955 895413407 803990450 21693588 866905388 169932411 340234047 259184127 331450756 506720779 194809709 896076578 936050255 925430496 741889050 638981221 628789074 358540287 89791215...

output:

224767283735

result:

wrong answer 1st numbers differ - expected: '226446817254', found: '224767283735'