oj.uz

Submission #90606

# Submission time Handle Problem Language Result Execution time Memory
90606 2018-12-22T21:00:36 Z jasony123123 KOVANICE (COI15_kovanice) C++11
100 / 100
 486 ms 66232 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/****************************************************************/

const int MAXM = 300100;
int N, M, W; // dist, num, weigh
v<pii> equ, les;
v<int> adjE[MAXM];
v<v<int>> adjNorm, adjRev;
int comp[MAXM], C = 0;
int dpNorm[MAXM], dpRev[MAXM], finalAns[MAXM];

int calc(int x, v<v<int>> &adj, int dp[]) {
	if (dp[x] > 0) return dp[x];
	for (int chi : adj[x])
		maxx(dp[x], calc(chi, adj, dp));
	dp[x] += 1;
	return dp[x];
}

void dfs(int x, int c) {
	if (comp[x] != -1) return;
	comp[x] = c;
	for (int child : adjE[x]) dfs(child, c);
}

int main() {
	io();
	cin >> N >> M >> W;
	FOR(i, 0, W) {
		int a, b;
		char c;
		cin >> a >> c >> b;
		if (c == '=')
			equ.push_back({ a,b });
		else
			les.push_back({ a,b });
	}

	// make comp
	for (pii x : equ)
		adjE[x.first].push_back(x.second), adjE[x.second].push_back(x.first);
	FORE(i, 1, M) comp[i] = -1;
	FORE(i, 1, M) 
		if (comp[i] == -1) 
			dfs(i, C++);

	// init adj for dp
	adjNorm.resize(C);
	adjRev.resize(C);
	for (pii x : les)
		adjNorm[comp[x.first]].push_back(comp[x.second]), adjRev[comp[x.second]].push_back(comp[x.first]);
	FOR(i, 0, C) {
		calc(i, adjNorm, dpNorm), calc(i, adjRev, dpRev);
	}

	// gen ans
	FOR(i, 0, C) {
		int ans1 = dpRev[i];
		int ans2 = N + 1 - dpNorm[i];
		if (ans1 != ans2) finalAns[i] = -1;
		else finalAns[i] = ans1;
	}
	FORE(i, 1, M) {
		if (finalAns[comp[i]] != -1) {
			cout << "K" << finalAns[comp[i]] << "\n";
		}
		else {
			cout << "?\n";
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7640 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 24812 KB Output is correct
2 Correct 127 ms 26624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 26624 KB Output is correct
2 Correct 26 ms 26624 KB Output is correct
3 Correct 29 ms 26624 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 45388 KB Output is correct
2 Correct 261 ms 48472 KB Output is correct
3 Correct 253 ms 52228 KB Output is correct
4 Correct 372 ms 61524 KB Output is correct
5 Correct 486 ms 66232 KB Output is correct