oj.uz

Submission #257646

# Submission time Handle Problem Language Result Execution time Memory
257646 2020-08-04T13:59:06 Z igm_igm Mag (COCI16_mag) C++14
108 / 120
 865 ms 228980 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];
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){
	vector<llo> kk;
	kk.pb(co);
	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.pb(dp[j]);
	}
	sort(all(kk));
	reverse(all(kk));
	llo cc=0;
	for(llo i=0;i<kk.size();i++){
		if(i==2){
			break;
		}
		cc+=kk[i];
	}
	remin({it[no],1+cc});
	if(it[no]==1){
		dp[no]=ma+1;
	}

}


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);
	cout<<ans.a<<"/"<<ans.b<<endl;



	return 0;
}

Compilation message

mag.cpp: In function 'void dfs(llo, llo, llo)':
mag.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo i=0;i<kk.size();i++){
              ~^~~~~~~~~~
mag.cpp: In function 'void setIO(std::__cxx11::string)':
mag.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((s+".in").c_str(),"r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mag.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((s+".out").c_str(),"w",stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23936 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23936 KB Output is correct
2 Correct 15 ms 23936 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 485 ms 131768 KB Output isn't correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 643 ms 225284 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 224008 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 865 ms 85880 KB Output is correct
2 Correct 413 ms 69736 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 94816 KB Output is correct
2 Correct 129 ms 30716 KB Output is correct
3 Correct 638 ms 228980 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 30460 KB Output is correct
2 Correct 543 ms 86908 KB Output is correct
3 Correct 535 ms 57984 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 85264 KB Output is correct
2 Correct 633 ms 87288 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 87036 KB Output is correct
2 Correct 414 ms 57976 KB Output is correct