oj.uz

Submission #286532

# Submission time Handle Problem Language Result Execution time Memory
286532 2020-08-30T14:08:49 Z FlashGamezzz Mag (COCI16_mag) C++11
84 / 120
 565 ms 262148 KB 
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>

using namespace std;

long n, minM = 1000000000, maxP = 0, mag[1000000], pd[1000000] = {}, path[1000000] = {}, pn[1000000] = {};
vector <long> adj[1000000], mi[1000000];

void dfs(int i, int p) {
	minM = min(minM, mag[i]);
	for (int a : adj[i]) {
		if (a != p) {
			dfs(a, i);
		}
	}
	if (mag[i] == 1) {
		pd[i] = 1;
		for (int a : adj[i]) {
			if (a != p && mag[a] == 1) {
				if (pd[a]+1 > pd[i]) {
					pd[i] = pd[a]+1;
					vector <long> t;
					t.push_back(a);
					mi[i] = t;
				} else if (pd[a]+1 == pd[i]) {
					mi[i].push_back(a);
				}
			}
		}
		path[i] = pd[i];
		if (mi[i].size() == 1){
			long mind = mi[i][0];
			vector <long> t;
			for (int a : adj[i]){
				if (a != p && mag[a] == 1 && a != mind ) {
					if (pd[i]+pd[a] > path[i]){
						path[i] = pd[i]+pd[a];
						vector <long> tt;
						tt.push_back(a);
						t = tt;
					} else if (pd[i]+pd[a] == path[i]){
						t.push_back(a);
					}
				}
			}
			for (int a : t){
				mi[i].push_back(a);
			}
		} else if (mi[i].size() > 1){
			path[i] = 2*pd[i]-1;
		}
		maxP = max(path[i], maxP);
	}
}
void dfs2(int i, int v){
	pn[i] = v;
	for (int a : mi[i]) {
		dfs2(a, v);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int a, b;
		cin >> a >> b;
		adj[a-1].push_back(b-1);
		adj[b-1].push_back(a-1);
	}
	for (int i = 0; i < n; i++) {
		cin >> mag[i];
	}
	dfs(0, -1);
	if (minM == 1){
		for (int i = 0; i < n; i++){
			if (path[i] == maxP){
				dfs2(i, i+1);
			}
		}
		bool twok = false;
		for (int i = 0; i < n; i++){
			if (mag[i] == 2){
				int count = 0;
				for (int a : adj[i]){
					if (pn[a] != 0){
						count++;
						if (count >= 2){
							twok = true;
							break;
						}
					}
				}
			}
		}
		if (twok){
			cout << "2/" << (2*maxP+1);
		} else {
			cout << "1/" << maxP;
		}
	} else {
		cout << minM << "/1";
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47480 KB Output is correct
2 Correct 30 ms 47484 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 198948 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47352 KB Output is correct
2 Runtime error 544 ms 262148 KB Execution killed with signal 9

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 560 ms 262148 KB Execution killed with signal 9

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 156028 KB Output is correct
2 Correct 424 ms 127480 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 129116 KB Output is correct
2 Correct 118 ms 57464 KB Output is correct
3 Runtime error 551 ms 262148 KB Execution killed with signal 9

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 56824 KB Output is correct
2 Correct 565 ms 157248 KB Output is correct
3 Correct 477 ms 96376 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 136804 KB Output is correct
2 Correct 550 ms 155640 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 153464 KB Output is correct
2 Correct 461 ms 94584 KB Output is correct