Submission #486402

#	Time	Username	Problem	Language	Result	Execution time	Memory
486402		groupATSU	Mag (COCI16_mag)	C++14	12 / 120	815 ms	48936 KiB

mag

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e9;
const int maxn=1e6+10;
const ll mod=1e9+7;
int n;
vector <int> g;
vector <ll> color(maxn);
vector <int> parent(maxn),sz(maxn);
int find_set(int v){
	if(parent[v]==v)return v;
	return parent[v]=find_set(parent[v]);
}
void union_set(int a,int b){
	a=find_set(a);
	b=find_set(b);
	if(a!=b){
		if(sz[b]>sz[a])swap(a,b);
		parent[a]=b;
		sz[b]+=sz[a];
	}
}
void solve(){
	int n;
	cin>>n;
	vector <pair<int,int>> b(n);
	for(int i=1;i<=n;i++){
		sz[i]=1;
		parent[i]=i;
	}
	for(int i=0;i<n-1;i++){
		cin>>b[i].first>>b[i].second;
	}
	for(int i=1;i<=n;i++)cin>>color[i];
	vector <int> vertex;
	int ind=0;
	for(int i=0;i<n-1;i++){
		if(color[b[i].first]==1 && color[b[i].second]==1){
			union_set(b[i].first,b[i].second);
			vertex.push_back(b[i].first);
			vertex.push_back(b[i].second);
			ind=1;
		}
	}
	if(ind==0){
		ll mn=1e10;
		for(int i=1;i<=n;i++){
			mn=min(mn,color[i]);	
		}
		cout<<mn<<"/"<<1;
	}else{
		int mx=-1;
		for(int i=0;i<vertex.size();i++){
			mx=max(mx,sz[find_set(vertex[i])]);
		}
		cout<<1<<"/"<<mx;
	}
}
int main(){
	//ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    int t=1;
   	//cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }


}

Compilation message (stderr)

mag.cpp: In function 'void solve()':
mag.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=0;i<vertex.size();i++){
      |               ~^~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12