oj.uz

답안 #335186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335186 2020-12-11T11:52:11 Z guka415 KOVANICE (COI15_kovanice) C++14
0 / 100
 66 ms 38508 KB 
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (long long i = k; i < n; i++)
#define ford(i, k, n) for (long long i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <bitset>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

const int sz = 5e5 + 5;

pair<pii, char> parse(string s) {
	int cur = 0, ind = 0, len = s.length();
	pair<pii, char> ret;
	while (ind < len&&s[ind] >= '0'&&s[ind] <= '9') {
		cur *= 10;
		cur += (s[ind++] - '0');
	}
	ret.first.first = cur;
	ret.second = s[ind++];
	cur = 0;
	while (ind < len&&s[ind] >= '0'&&s[ind] <= '9') {
		cur *= 10;
		cur += (s[ind++] - '0');
	}
	ret.first.second = cur;
	return ret;
}

struct dsu {
	int f[sz], p[sz];
	int n;
	dsu(int size) {
		n = size;
		foru(i, 0, n) {
			p[i] = 1;
			f[i] = i;
		}
	}
	int father(int src) {
		while (src != f[src])return f[src] = father(f[src]);
	}
	bool unite(int a, int b) {
		int fa = father(a), fb = father(b);
		if (fa == fb)return false;
		if (p[fa] < p[fb])swap(fa, fb);
		f[fb] = fa;
		p[fa] = max(p[fb] + 1, p[fa]);
		return true;
	}
};

vector<int> unadj[sz], adj[sz], radj[sz];
int coins, mirk, v, ans[sz], indeg[sz], dp[sz];
dsu* d;
bitset<sz> isf, vis;

void input() {
	cin >> coins >> mirk >> v;
	d = new dsu(mirk);
	foru(i, 0, v) {
		string s;
		cin >> s;
		/*pair<pii, char> p = parse(s);
		p.first.first--; p.first.second--;
		switch (p.second) {
		case '=':
			d->unite(p.first.first, p.first.second);
			break;
		case '<':
			unadj[p.first.first].pb(p.first.second);
			break;
		case '>':
			unadj[p.first.second].pb(p.first.first);
			break;
		}*/
	}
	/*foru(i, 0, mirk) {
		int myf = d->father(i);
		isf[myf] = 1;
		for (int x : unadj[i]) {
			int otherf = d->father(x);
			adj[myf].pb(otherf); radj[otherf].pb(myf);
			indeg[otherf]++;
		}
	}*/
}

void dfs(int src) {
	vis[src] = 1;
	ans[src] = dp[src];
	for (int x : radj[src]) {
		if (!vis[x] && dp[x] == dp[src] - 1)dfs(x);
	}
}

int main() {
	fast;
	input();
	/*queue<int> q;
	foru(i, 0, mirk) {
		if (isf[i] && indeg[i] == 0)q.push(i);
	}
	while (!q.empty()) {
		int x = q.front(); q.pop();
		dp[x] = 1;
		for (int y : radj[x])dp[x] = max(dp[x], dp[y] + 1);
		for (int y : adj[x]) {
			indeg[y]--;
			if (indeg[y] == 0)q.push(y);
		}
	}
	foru(i, 0, mirk) {
		if (dp[i] == coins)dfs(i);
	}*/
	foru(i, 0, mirk) {
		int myf = 3;
		if (ans[myf] != 0)cout << 'K' << to_string(ans[myf]) << '\n';
		else cout << "?\n";
	}
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 40.0

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