oj.uz

Submission #78807

# Submission time Handle Problem Language Result Execution time Memory
78807 2018-10-09T03:57:32 Z tmwilliamlin168 KOVANICE (COI15_kovanice) C++14
100 / 100
 439 ms 34480 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=3e5;
int n, m, v, p[mxN], r[mxN], a[mxN], b[mxN], dp[2][mxN];
vector<int> adj[2][mxN];

int root(int x) {
	return p[x]==x?x:(p[x]=root(p[x]));
}

void join(int x, int y) {
	if((x=root(x))==(y=root(y)))
		return;
	if(r[x]<r[y])
		p[x]=y;
	else
		p[y]=x;
	r[x]+=r[x]==r[y];
}

int cdp(int a, int u) {
	if(!dp[a][u]) {
		dp[a][u]=a?n:1;
		for(int v : adj[a][u])
			dp[a][u]=a?min(cdp(a, v)-1, dp[a][u]):max(cdp(a, v)+1, dp[a][u]);
	}
	return dp[a][u];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> v;
	for(int i=0; i<m; ++i)
		p[i]=i;
	for(int i=0; i<v; ++i) {
		char qt;
		cin >> a[i] >> qt >> b[i], --a[i], --b[i];
		if(qt=='=') {
			join(a[i], b[i]);
			a[i]=-1;
		}
	}
	for(int i=0; i<v; ++i) {
		if(a[i]!=-1) {
			adj[0][root(b[i])].push_back(root(a[i]));
			adj[1][root(a[i])].push_back(root(b[i]));
		}
	}
	for(int i=0; i<m; ++i)
		cout << (cdp(0, root(i))==cdp(1, root(i))?"K"+to_string(cdp(0, root(i))):"?") << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14584 KB Output is correct
2 Correct 16 ms 14716 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 21548 KB Output is correct
2 Correct 127 ms 21604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 21604 KB Output is correct
2 Correct 37 ms 21604 KB Output is correct
3 Correct 38 ms 21604 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 30516 KB Output is correct
2 Correct 319 ms 30516 KB Output is correct
3 Correct 341 ms 30516 KB Output is correct
4 Correct 385 ms 33712 KB Output is correct
5 Correct 439 ms 34480 KB Output is correct