oj.uz

Submission #61503

# Submission time Handle Problem Language Result Execution time Memory
61503 2018-07-26T06:00:16 Z 김세빈(#1779) Min-max tree (BOI18_minmaxtree) C++11
22 / 100
 179 ms 10236 KB 
#include <bits/stdc++.h>

using namespace std;

struct chain
{
	int s, e, v;
	chain() {}
	chain(int s, int e, int v) : s(s), e(e), v(v) {}
};

vector <chain> X, Y;
vector <int> V[70707], T;
int P[70707], K[70707], C[70707], D[70707];
int n, k;

void dfs(int p, int r)
{
	P[p] = K[p] = r;
	D[p] = D[r] + 1;
	for(int t: V[p]){
		if(t != r) dfs(t, p);
	}
}

int main()
{
	int i, a, b, c;
	char str[3];
	
	scanf("%d", &n);
	
	for(i=1; i<n; i++){
		scanf("%d%d", &a, &b);
		V[a].push_back(b);
		V[b].push_back(a);
	}
	
	dfs(1, 0);
	
	scanf("%d", &k);
	
	for(i=1; i<=k; i++){
		scanf("%s%d%d%d", str, &a, &b, &c);
		if(*str == 'M'){
			X.push_back(chain(a, b, c));
		}
		else{
			Y.push_back(chain(a, b, c));
		}
	}
	
	sort(X.begin(), X.end(), [=](chain ca, chain cb){
		return ca.v < cb.v;
	});
	
	for(i=0; i<X.size(); i++){
		a = X[i].s, b = X[i].e, c = X[i].v;
		T.clear();
		
		for(; a!=b; ){
			if(D[a] < D[b]) swap(a, b);
			if(C[a] == 0) C[a] = X[i].v;
			T.push_back(a); a = K[a];
		}
		
		for(int t: T) K[t] = a;
	}
	
	for(i=2; i<=n; i++){
		printf("%d %d %d\n", i, P[i], C[i]? C[i] : 12345);
	}
	
	return 0;
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<X.size(); i++){
           ~^~~~~~~~~
minmaxtree.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
minmaxtree.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
minmaxtree.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%d%d", str, &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 9688 KB Output is correct
2 Correct 131 ms 9688 KB Output is correct
3 Correct 131 ms 9688 KB Output is correct
4 Correct 179 ms 10236 KB Output is correct
5 Correct 158 ms 10236 KB Output is correct
6 Correct 162 ms 10236 KB Output is correct
7 Correct 131 ms 10236 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 10236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -