Submission #274458

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274458	2020-08-19T12:03:51 Z	kshitij_sodani	Mag (COCI16_mag)	C++14	120 / 120	651 ms	262144 KB

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define all(x) x.begin(),x.end()
void setIO(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
 
pair<llo,llo> ans;
vector<llo> adj[1000001];
vector<pair<llo,llo>> kk[1000001];
llo it[1000001];
llo dp[1000001];
llo n;
void remin(pair<llo,llo> xx){
	llo yo=__gcd(xx.a,xx.b);
	xx.a/=yo;
	xx.b/=yo;
	if(xx.a*ans.b<xx.b*ans.a){
		ans=xx;
	}
}
void dfs(llo no,llo par=-1,llo co=0){
	co+=1;
	if(it[no]>1){
		co=0;
	}
	llo ma=0;
	for(auto j:adj[no]){
		if(j==par){
			continue;
		}
		dfs(j,no,co);
		ma=max(ma,dp[j]);
		kk[no].pb({dp[j],j});
	}
	sort(all(kk[no]));
	reverse(all(kk[no]));
	llo cc=0;
	for(llo i=0;i<kk[no].size();i++){
		if(i==2){
			break;
		}
		cc+=kk[no][i].a;
	}
	remin({it[no],1+cc});
	if(it[no]==1){
		dp[no]=ma+1;
	}
}
void dfs2(llo no,llo par=-1,llo co=0){
	llo kp=co+1;
	if(kk[no].size()){
		kp+=kk[no][0].a;
	}
	remin({it[no],kp});
	if(it[no]==1){
		co+=1;
	}
	else{
		co=0;
	}
	llo ma=0;
	for(auto j:adj[no]){
		if(j==par){
			continue;
		}
		llo se=0;
		if(it[no]==1){
			se=max(se,co);
			llo su=1;
			for(int i=0;i<2;i++){
				if(i==kk[no].size()){
					break;
				}
				if(kk[no][i].b==j){
					continue;
				}
				su+=kk[no][i].a;
				break;
			}
			se=max(se,su);
		}
		dfs2(j,no,se);
	}
 
 
}
 
 
 
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n-1;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	ans={it[0],1};
	dfs(0);
	dfs2(0);
	cout<<ans.a<<"/"<<ans.b<<endl;
 
 
 
	return 0;
}

Compilation message

mag.cpp: In function 'void dfs(llo, llo, llo)':
mag.cpp:45:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(llo i=0;i<kk[no].size();i++){
      |              ~^~~~~~~~~~~~~~
mag.cpp: In function 'void dfs2(llo, llo, llo)':
mag.cpp:78:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     if(i==kk[no].size()){
      |        ~^~~~~~~~~~~~~~~
mag.cpp:68:6: warning: unused variable 'ma' [-Wunused-variable]
   68 |  llo ma=0;
      |      ^~
mag.cpp: In function 'void setIO(std::string)':
mag.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   10 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mag.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   11 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	47352 KB	Output is correct
2	Correct	32 ms	47360 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	47352 KB	Output is correct
2	Correct	31 ms	47360 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	493 ms	173820 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	47332 KB	Output is correct
2	Correct	625 ms	262144 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	651 ms	254032 KB	Output is correct

Subtask #6
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	560 ms	140408 KB	Output is correct
2	Correct	443 ms	115916 KB	Output is correct

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	492 ms	128980 KB	Output is correct
2	Correct	134 ms	56696 KB	Output is correct
3	Correct	598 ms	256760 KB	Output is correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	126 ms	56596 KB	Output is correct
2	Correct	528 ms	141432 KB	Output is correct
3	Correct	505 ms	94328 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	487 ms	134780 KB	Output is correct
2	Correct	517 ms	132004 KB	Output is correct

Subtask #10
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	534 ms	141920 KB	Output is correct
2	Correct	525 ms	94352 KB	Output is correct