oj.uz

Submission #61535

# Submission time Handle Problem Language Result Execution time Memory
61535 2018-07-26T07:15:12 Z khsoo01 Min-max tree (BOI18_minmaxtree) C++11
0 / 100
 182 ms 14804 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

const int N = 70005;

int n, m, dep[N], par[N], ans[N];
bool vv[N], ve[N];

vector<int> tr[N], cyc, usd;
vector<pii> adj[N];

struct edge {
	int a, b, x;
	bool operator < (edge &T) {
		return x < T.x;
	}
} e[N];

struct coloring {
	int c[N], p[N];
	int Find (int X) {
		if(p[X] == X) return X;
		return p[X] = Find(p[X]);
	}
	void init () {
		for(int i=1;i<=n;i++) {
			c[i] = 0;
			p[i] = i;
		}
	}
	void color (int A, int B, int C) {
		while(true) {
			A = Find(A);
			B = Find(B);
			if(dep[A] == dep[B]) return;
			if(dep[A] < dep[B]) swap(A, B);
			c[A] = C;
			p[A] = par[A];
		}
	}
} col[2];

void calc (int C, int P) {
	dep[C] = dep[P] + 1;
	par[C] = P;
	for(auto &T : tr[C]) {
		if(T == P) continue;
		calc(T, C);
	}
}

bool findcyc (int I) {
	if(vv[I]) return true;
	vv[I] = true;
	for(auto &T : adj[I]) {
		int A, B;
		tie(A, B) = T;
		if(ve[B]) continue;
		ve[B] = true;
		if(findcyc(A)) {
			cyc.push_back(I);
			ans[B] = I;
			return true;
		}
	}
	usd.push_back(I);
	return false;
}

void dfs (int I) {
	vv[I] = true;
	for(auto &T : adj[I]) {
		int A, B;
		tie(A, B) = T;
		if(vv[A]) continue;
		ans[B] = A;
		dfs(A);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		tr[A].push_back(B);
		tr[B].push_back(A);
	}
	calc(1, 0);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) {
		char typ[2];
		scanf("%s%d%d%d",typ,&e[i].a,&e[i].b,&e[i].x);
		if(typ[0] == 'm') e[i].x *= -1;
	}
	sort(e+1, e+1+m);
	col[0].init();
	col[1].init();
	for(int i=1;i<=m;i++) {
		col[e[i].x > 0].color(e[i].a, e[i].b, i);
	}
	for(int i=1;i<=n;i++) {
		int A = col[0].c[i], B = col[1].c[i];
		adj[A].push_back({B, i});
		adj[B].push_back({A, i});
	}
	for(int i=0;i<=m;i++) {
		if(vv[i]) continue;
		findcyc(i);
		for(auto &T : usd) {
			vv[T] = false;
		}
		usd.clear();
		for(auto &T : cyc) {
			dfs(T);
		}
		cyc.clear();
	}
	for(int i=2;i<=n;i++) {
		int T = 1;
		if(ans[i]) T = ans[i];
		else if(col[0].c[i]) T = col[0].c[i];
		else if(col[1].c[i]) T = col[1].c[i];
		printf("%d %d %d\n", par[i], i, abs(e[T].x));
	}
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:87: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:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
minmaxtree.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%d%d",typ,&e[i].a,&e[i].b,&e[i].x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

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