oj.uz

Submission #25741

# Submission time Handle Problem Language Result Execution time Memory
25741 2017-06-24T03:27:09 Z dotorya 한자 끝말잇기 (JOI14_kanji) C++14
100 / 100
 366 ms 23800 KB 
#include "Annalib.h"

#include <map>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

map <pii, int> Mx;
ll in[305][305];

ll disa[305][305];
int reva[305][305];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
	int i, j, k;
	for (i = 0; i < N; i++) for (j = 0; j < N; j++) if (i != j) disa[i][j] = LL_INF, reva[i][j] = i;
	for (i = 0; i < M; i++) {
		disa[A[i]][B[i]] = C[i];
		reva[A[i]][B[i]] = A[i];
	}
	for (i = 0; i < K; i++) Mx[pii(A[U[i]], B[U[i]])] = i;

	for (k = 0; k < N; k++) {
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				if (disa[i][j] > disa[i][k] + disa[k][j]) {
					disa[i][j] = disa[i][k] + disa[k][j];
					reva[i][j] = reva[k][j];
				}
			}
		}
	}

	int c[6] = { 0, };
	for (i = 0; i < Q; i++) {
		int s = S[i], e = T[i];
		int v = K;
		while (e != s) {
			int t = reva[s][e];
			if (Mx.count(pii(t, e))) v = Mx[pii(t, e)];
			e = t;
		}
		c[v]++;
	}
	for (i = 0; i <= K; i++) {
		for (j = 5; j >= 0; j--) {
			if (c[i] & (1 << j)) Tap(1);
			else Tap(0);
		}
	}
}

#include "Brunolib.h"

#include <map>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

const ll MOD2 = 1000000000000000000ll;
pll operator + (pll a, pll b) {
	pll rv = pll(a.first + b.first, a.second + b.second);
	if (rv.second >= MOD2) {
		rv.first++;
		rv.second -= MOD2;
	}
	return rv;
}
pll operator - (pll a, pll b) {
	pll rv = pll(a.first - b.first, a.second - b.second);
	if (rv.second < 0) {
		rv.first--;
		rv.second += MOD2;
	}
	return rv;
}
pll operator - (pll a) {
	pll rv = pll(-a.first, -a.second);
	if (rv.second < 0) {
		rv.first--;
		rv.second += MOD2;
	}
	return rv;
}

class edge {
public:
	int s, e, f;
	pll c;
	edge() {
		*this = edge(0, 0, 0, pll(0,0));
	}
	edge(int s, int e, int f, pll c) : s(s), e(e), f(f), c(c) {}
};
vector <edge> E;
vector <int> fconn[100050];

void epush(int s, int e, int f, pll c) {
	edge e1 = edge(s, e, f, c);
	edge e2 = edge(e, s, 0, -c);
	fconn[s].push_back(E.size());
	fconn[e].push_back(E.size() + 1);
	E.push_back(e1);
	E.push_back(e2);
}

pll fdis[100050];
int frev[100050];
bool fchk[100050];
vector <int> Vf;
ll totc = 0;
int BellmanFord(int snk) {
	fill(fdis, fdis + snk + 1, pll(LL_INF, LL_INF));
	fill(frev, frev + snk + 1, -1);
	fill(fchk, fchk + snk + 1, false);
	fchk[0] = true;
	fdis[0] = pll(0, 0);
	Vf.push_back(0);
	for (int i = 0; i < Vf.size(); i++) {
		fchk[Vf[i]] = false;
		for (auto it : fconn[Vf[i]]) {
			if (E[it].f == 0 || fdis[E[it].e] <= fdis[Vf[i]] + E[it].c) continue;
			fdis[E[it].e] = fdis[Vf[i]] + E[it].c;
			frev[E[it].e] = it;
			if (!fchk[E[it].e]) {
				Vf.push_back(E[it].e);
				fchk[E[it].e] = true;
			}
		}
	}
	Vf.clear();

	if (fdis[snk] == pll(LL_INF, LL_INF)) return 0;

	int f = INF;
	int t = snk;
	while (t) {
		f = min(f, E[frev[t]].f);
		t = E[frev[t]].s;
	}
	t = snk;
	while (t) {
		E[frev[t]].f -= f;
		E[frev[t] ^ 1].f += f;
		t = E[frev[t]].s;
	}
	return f;
}
int getFlow(int snk) {
	totc = 0;
	int f = 0, t;
	while (t = BellmanFord(snk)) f += t;
	return f;
}
void init(int snk) {
	for (int i = 0; i <= snk; i++) fconn[i].clear();
	E.clear();
}

pll disb[305][305];
int revb[305][305];
pll getv(ll a) {
	pll rv = pll(a / MOD2, a % MOD2);
	if (rv.second < 0) {
		rv.second += MOD2;
		rv.first--;
	}
	return rv;
}

void getr(int s, int e, vector<int>& Vu) {
	while (e != s) {
		Vu.push_back(e);
		e = revb[s][e];
	}
	Vu.push_back(s);
}

map <pii, int> Mxb;
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
	int i, j, k;
	for (i = 0; i < N; i++) for (j = 0; j < N; j++) if (i != j) disb[i][j] = getv(LL_INF), revb[i][j] = i;
	for (i = 0; i < M; i++) Mxb[pii(A[i], B[i])] = i;
	for (i = 0; i < M; i++) {
		if (C[i] != -1) {
			disb[A[i]][B[i]] = getv(C[i]);
			revb[A[i]][B[i]] = A[i];
		}
	}

	for (k = 0; k < N; k++) {
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				if (disb[i][j] > disb[i][k] + disb[k][j]) {
					disb[i][j] = disb[i][k] + disb[k][j];
					revb[i][j] = revb[k][j];
				}
			}
		}
	}

	int v[6] = { 0, };
	for (i = 0; i <= K; i++) {
		for (j = 0; j < 6; j++) v[i] = 2 * v[i] + X[i * 6 + j];
	}

	ll src = 0, snk = Q + K + 2;
	for (i = 0; i < Q; i++) {
		for (j = 0; j <= K; j++) {
			pll v = pll(0, 0);
			if (j < K) v = (disb[S[i]][A[U[j]]] + disb[B[U[j]]][T[i]]) - disb[S[i]][T[i]];
			epush(i + 1, Q + j + 1, 1, v);
		}
	}
	for (i = 0; i < Q; i++) epush(src, i + 1, 1, getv(0));
	for (i = 0; i <= K; i++) epush(Q + i + 1, snk, v[i], getv(0));

	int f = getFlow(snk);
	for (i = 0; i < Q; i++) {
		for (j = 0; j <= K; j++) {
			int p = (i * (K + 1) + j) * 2;
			if (!E[p].f) break;
		}
		
		vector <int> Vu;
		if (j == K) getr(S[i], T[i], Vu);
		else {
			getr(B[U[j]], T[i], Vu);
			getr(S[i], A[U[j]], Vu);
		}
		reverse(Vu.begin(), Vu.end());
		for (j = 0; j + 1 < Vu.size(); j++) Answer(Mxb[pii(Vu[j], Vu[j + 1])]);
		Answer(-1);
	}
}

Compilation message

Bruno.cpp: In function 'int BellmanFord(int)':
Bruno.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Vf.size(); i++) {
                    ^
Bruno.cpp: In function 'int getFlow(int)':
Bruno.cpp:107:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  while (t = BellmanFord(snk)) f += t;
                            ^
Bruno.cpp: In function 'void Bruno(int, int, int*, int*, long long int*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:187:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j + 1 < Vu.size(); j++) Answer(Mxb[pii(Vu[j], Vu[j + 1])]);
                     ^
Bruno.cpp:173:6: warning: unused variable 'f' [-Wunused-variable]
  int f = getFlow(snk);
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 18260 KB Output is correct - L = 36
2 Correct 119 ms 18260 KB Output is correct - L = 36
3 Correct 119 ms 18260 KB Output is correct - L = 36
4 Correct 105 ms 18124 KB Output is correct - L = 36
5 Correct 102 ms 18124 KB Output is correct - L = 36
6 Correct 98 ms 18124 KB Output is correct - L = 36
7 Correct 89 ms 18124 KB Output is correct - L = 36
8 Correct 111 ms 18256 KB Output is correct - L = 36
9 Correct 129 ms 18256 KB Output is correct - L = 36
10 Correct 125 ms 18388 KB Output is correct - L = 36
11 Correct 98 ms 18124 KB Output is correct - L = 36
12 Correct 302 ms 23800 KB Output is correct - L = 36
13 Correct 114 ms 18260 KB Output is correct - L = 36
14 Correct 118 ms 18124 KB Output is correct - L = 12

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 18260 KB Output is correct - L = 36
2 Correct 95 ms 18260 KB Output is correct - L = 36
3 Correct 112 ms 18260 KB Output is correct - L = 36
4 Correct 148 ms 18260 KB Output is correct - L = 36
5 Correct 126 ms 18260 KB Output is correct - L = 36
6 Correct 129 ms 18260 KB Output is correct - L = 36
7 Correct 116 ms 18260 KB Output is correct - L = 36
8 Correct 132 ms 18260 KB Output is correct - L = 36
9 Correct 109 ms 18256 KB Output is correct - L = 36
10 Correct 109 ms 18256 KB Output is correct - L = 36
11 Correct 105 ms 18256 KB Output is correct - L = 36
12 Correct 116 ms 18260 KB Output is correct - L = 36
13 Correct 322 ms 23800 KB Output is correct - L = 36
14 Correct 119 ms 18260 KB Output is correct - L = 36
15 Correct 138 ms 18260 KB Output is correct - L = 36
16 Correct 119 ms 18388 KB Output is correct - L = 36
17 Correct 159 ms 18388 KB Output is correct - L = 36
18 Correct 135 ms 18652 KB Output is correct - L = 36
19 Correct 129 ms 18260 KB Output is correct - L = 36
20 Correct 155 ms 18784 KB Output is correct - L = 36
21 Correct 129 ms 18784 KB Output is correct - L = 36
22 Correct 106 ms 18256 KB Output is correct - L = 36
23 Correct 95 ms 18256 KB Output is correct - L = 36
24 Correct 108 ms 18256 KB Output is correct - L = 36

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 18260 KB Output is correct - L = 36
2 Correct 95 ms 18260 KB Output is correct - L = 36
3 Correct 106 ms 18260 KB Output is correct - L = 36
4 Correct 112 ms 18260 KB Output is correct - L = 36
5 Correct 109 ms 18260 KB Output is correct - L = 36
6 Correct 119 ms 18260 KB Output is correct - L = 36
7 Correct 119 ms 18260 KB Output is correct - L = 36
8 Correct 114 ms 18260 KB Output is correct - L = 36
9 Correct 112 ms 18256 KB Output is correct - L = 36
10 Correct 102 ms 18256 KB Output is correct - L = 36
11 Correct 106 ms 18256 KB Output is correct - L = 36
12 Correct 112 ms 18260 KB Output is correct - L = 36
13 Correct 345 ms 23800 KB Output is correct - L = 36
14 Correct 142 ms 18260 KB Output is correct - L = 36
15 Correct 128 ms 18260 KB Output is correct - L = 36
16 Correct 129 ms 18388 KB Output is correct - L = 36
17 Correct 132 ms 18388 KB Output is correct - L = 36
18 Correct 132 ms 18652 KB Output is correct - L = 36
19 Correct 118 ms 18260 KB Output is correct - L = 36
20 Correct 111 ms 18784 KB Output is correct - L = 36
21 Correct 132 ms 18784 KB Output is correct - L = 36
22 Correct 105 ms 18256 KB Output is correct - L = 36
23 Correct 122 ms 18256 KB Output is correct - L = 36
24 Correct 109 ms 18256 KB Output is correct - L = 36

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 18260 KB Output is correct - L = 36
2 Correct 106 ms 18260 KB Output is correct - L = 36
3 Correct 112 ms 18260 KB Output is correct - L = 36
4 Correct 99 ms 18260 KB Output is correct - L = 36
5 Correct 111 ms 18260 KB Output is correct - L = 36
6 Correct 132 ms 18260 KB Output is correct - L = 36
7 Correct 106 ms 18260 KB Output is correct - L = 36
8 Correct 119 ms 18260 KB Output is correct - L = 36
9 Correct 109 ms 18256 KB Output is correct - L = 36
10 Correct 111 ms 18256 KB Output is correct - L = 36
11 Correct 119 ms 18256 KB Output is correct - L = 36
12 Correct 129 ms 18260 KB Output is correct - L = 36
13 Correct 366 ms 23800 KB Output is correct - L = 36
14 Correct 136 ms 18260 KB Output is correct - L = 36
15 Correct 128 ms 18260 KB Output is correct - L = 36
16 Correct 138 ms 18388 KB Output is correct - L = 36
17 Correct 129 ms 18388 KB Output is correct - L = 36
18 Correct 138 ms 18652 KB Output is correct - L = 36
19 Correct 122 ms 18260 KB Output is correct - L = 36
20 Correct 119 ms 18784 KB Output is correct - L = 36
21 Correct 152 ms 18784 KB Output is correct - L = 36
22 Correct 136 ms 18256 KB Output is correct - L = 36
23 Correct 106 ms 18256 KB Output is correct - L = 36
24 Correct 122 ms 18256 KB Output is correct - L = 36

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 18260 KB Output is correct - L = 36
2 Correct 102 ms 18260 KB Output is correct - L = 36
3 Correct 102 ms 18260 KB Output is correct - L = 36
4 Correct 111 ms 18260 KB Output is correct - L = 36
5 Correct 119 ms 18260 KB Output is correct - L = 36
6 Correct 114 ms 18260 KB Output is correct - L = 36
7 Correct 128 ms 18260 KB Output is correct - L = 36
8 Correct 112 ms 18260 KB Output is correct - L = 36
9 Correct 98 ms 18256 KB Output is correct - L = 36
10 Correct 108 ms 18256 KB Output is correct - L = 36
11 Correct 105 ms 18256 KB Output is correct - L = 36
12 Correct 119 ms 18260 KB Output is correct - L = 36
13 Correct 309 ms 23800 KB Output is correct - L = 36
14 Correct 112 ms 18260 KB Output is correct - L = 36
15 Correct 125 ms 18260 KB Output is correct - L = 36
16 Correct 132 ms 18388 KB Output is correct - L = 36
17 Correct 119 ms 18388 KB Output is correct - L = 36
18 Correct 119 ms 18652 KB Output is correct - L = 36
19 Correct 139 ms 18260 KB Output is correct - L = 36
20 Correct 128 ms 18784 KB Output is correct - L = 36
21 Correct 136 ms 18784 KB Output is correct - L = 36
22 Correct 122 ms 18256 KB Output is correct - L = 36
23 Correct 98 ms 18256 KB Output is correct - L = 36
24 Correct 99 ms 18256 KB Output is correct - L = 36