oj.uz

답안 #486402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486402 2021-11-11T15:00:10 Z groupATSU Mag (COCI16_mag) C++14
12 / 120
 815 ms 48936 KB 
#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

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.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15968 KB Output is correct
2 Correct 7 ms 15948 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 15948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 815 ms 46636 KB Output isn't correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 15948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 800 ms 48796 KB Output isn't correct

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 698 ms 47380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 759 ms 40860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 19260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 728 ms 46920 KB Output is correct
2 Incorrect 795 ms 48936 KB Output isn't correct

Subtask #10
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 780 ms 47568 KB Output is correct
2 Incorrect 429 ms 31704 KB Output isn't correct