oj.uz

답안 #645997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
645997 2022-09-28T12:58:42 Z ghostwriter 친구 (IOI14_friend) C++14
100 / 100
 24 ms 8020 KB 
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
namespace subtask1 {
	const int N = 10;
	int c[N], d1[N][N], rs = 0;
	void brute(int n, int confidence[], int i, int s) {
		if (i >= n) {
			bool ok = 1;
			FRN(x, n)
			FRN(y, n) {
				if (x == y || !c[x] || !c[y]) continue;
				if (d1[x][y]) ok = 0;
			}
			if (ok) rs = max(rs, s);
			return;
		}
		brute(n, confidence, i + 1, s);
		c[i] = 1;
		brute(n, confidence, i + 1, s + confidence[i]);
		c[i] = 0;
	}
	int findSample(int n, int confidence[], int host[], int protocol[]) {
		FOR(i, 1, n - 1) {
			int h = host[i], p = protocol[i];
			if (!p) d1[i][h] = d1[h][i] = 1;
			else if (p == 1) {
				FRN(j, n)
					if (d1[h][j])
						d1[i][j] = d1[j][i] = 1;
			}
			else {
				FRN(j, n)
					if (d1[h][j])
						d1[i][j] = d1[j][i] = 1;
				d1[i][h] = d1[h][i] = 1;
			}
		}
		brute(n, confidence, 0, 0);
		return rs;
	}
}
namespace subtask2 {
	int rs = 0;
	int findSample(int n, int confidence[], int host[], int protocol[]) {
		FRN(i, n) rs += confidence[i];
		return rs;
	}
}
namespace subtask3 {
	int rs = 0;
	int findSample(int n, int confidence[], int host[], int protocol[]) {
		FRN(i, n) rs = max(rs, confidence[i]);
		return rs;
	}
}
namespace subtask4 {
	const int N = 1e3;
	int d[N][2], confidence[N];
	vi adj[N];
	void dfs(int u, int p) {
		int s0 = 0, s1 = 0;
		EACH(v, adj[u]) {
			if (v == p) continue;
			dfs(v, u);
			s0 += d[v][0];
			s1 += d[v][1];
		}
		d[u][0] = max(confidence[u] + s1, s0);
		d[u][1] = s0;
	}
	int findSample(int n, int confidence[], int host[], int protocol[]) {
		FRN(i, n) subtask4::confidence[i] = confidence[i];
		FOR(i, 1, n - 1) {
			int u = i, v = host[i];
			adj[u].pb(v);
			adj[v].pb(u);
		}
		dfs(0, -1);
		return d[0][0];
	}
}
namespace subtask5 {
	const int oo = 1e9 + 5;
	const int N = 1e3 + 2;
	int n, c[N], pre[N], ptr[N], dis[N], capacity[N][N], d1[N][N], confidence[N], source, sink;
	void bfs(int source) {
		FRN(i, n) dis[i] = oo;
		dis[source] = 0;
		queue<int> q;
		q.push(source);
		WHILE(!q.empty()) {
			int u = q.ft();
			q.pop();
			FRN(v, n) {
				if (!capacity[u][v] || dis[v] < oo) continue;
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
	int findBlockingFlow(int u, int flow) {
		if (!flow) return 0;
		if (u == sink) return flow;
		WHILE(ptr[u] < n) {
			int v = ptr[u]++;
			if (!capacity[u][v] || dis[v] != dis[u] + 1) continue;
			int f = findBlockingFlow(v, min(flow, capacity[u][v]));
			if (f) {
				pre[v] = u;
				return f;
			}
		}
		return 0;
	}
	int dinic() {
		int rs = 0;
		WHILE(1) {
			bfs(source);
			memset(ptr, 0, sizeof ptr);
			int f = findBlockingFlow(source, oo);
			if (!f) break;
			WHILE(f) {
				rs += f;
				int cur = sink;
				WHILE(cur != source) {
					int prev = pre[cur];
					capacity[prev][cur] = 0;
					capacity[cur][prev] = 1;
					cur = prev;
				}
				f = findBlockingFlow(source, oo);
			}
		}
		return rs;
	}
	int findSample(int n, int confidence[], int host[], int protocol[]) {
		subtask5::n = n;
		FRN(i, n) subtask4::confidence[i] = confidence[i];
		FOR(i, 1, n - 1) {
			int u = i, v = host[i], p = protocol[i];
			if (p == 0) {
				d1[u][v] = d1[v][u] = 1;
				c[u] = c[v] ^ 1;
			}
			else {
				FRN(j, n)
					if (d1[v][j])
						d1[u][j] = d1[j][u] = 1;
				c[u] = c[v];
			}
		}
		source = subtask5::n++;
		sink = subtask5::n++;
		FRN(i, n)
			if (c[i]) capacity[source][i] = 1;
			else capacity[i][sink] = 1;
		FRN(i, n)
		FRN(j, n) {
			if (!d1[i][j] || !c[i]) continue;
			capacity[i][j] = 1;
		}
		return n - dinic();
	}
}
namespace solution {
	const int N = 1e5;
	int p[N], q[N];
	int findSample(int n, int confidence[], int host[], int protocol[]) {
		FRN(i, n) p[i] = confidence[i];
		FOS(i, n - 1, 1) {
			int x = host[i], y = i, t = protocol[i];
			if (!t) {
				p[x] = max(p[x] + q[y], q[x] + p[y]);
				q[x] = max(q[x] + q[y], q[x] + p[y]);
			}
			else if (t == 1) {
				p[x] = max({q[x] + q[y], p[x] + q[y], q[x] + p[y], p[x] + p[y]});
				q[x] = q[x] + q[y];
			}
			else {
				p[x] = max(p[x] + q[y], q[x] + p[y]);
				q[x] = q[x] + q[y];
			}
		}
		return max(p[0], q[0]);
	}
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
	if (n <= 10) return subtask1::findSample(n, confidence, host, protocol);
	bool sub2 = (n <= 1e3), sub3 = (n <= 1e3), sub4 = (n <= 1e3), sub5 = (n <= 1000);
	FRN(i, n)
		if (confidence[i] != 1)
			sub5 = 0;
	FOR(i, 1, n - 1) {
		if (protocol[i] != 1) sub2 = 0;
		if (protocol[i] != 2) sub3 = 0;
		if (protocol[i] != 0) sub4 = 0;
		if (protocol[i] == 2) sub5 = 0;
	}
	if (sub2) return subtask2::findSample(n, confidence, host, protocol);
	if (sub3) return subtask3::findSample(n, confidence, host, protocol);
	if (sub4) return subtask4::findSample(n, confidence, host, protocol);
	if (sub5) return subtask5::findSample(n, confidence, host, protocol);
	return solution::findSample(n, confidence, host, protocol);
}
/*
6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0

2
10 20
0 1

2
10 20
0 0

3
1 1 1
0 0 0 1
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

Compilation message

friend.cpp: In function 'void subtask1::brute(int, int*, int, int)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:57:4: note: in expansion of macro 'FRN'
   57 |    FRN(x, n)
      |    ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:58:4: note: in expansion of macro 'FRN'
   58 |    FRN(y, n) {
      |    ^~~
friend.cpp: In function 'int subtask1::findSample(int, int*, int*, int*)':
friend.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
friend.cpp:71:3: note: in expansion of macro 'FOR'
   71 |   FOR(i, 1, n - 1) {
      |   ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:75:5: note: in expansion of macro 'FRN'
   75 |     FRN(j, n)
      |     ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:80:5: note: in expansion of macro 'FRN'
   80 |     FRN(j, n)
      |     ^~~
friend.cpp: In function 'int subtask2::findSample(int, int*, int*, int*)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:93:3: note: in expansion of macro 'FRN'
   93 |   FRN(i, n) rs += confidence[i];
      |   ^~~
friend.cpp: In function 'int subtask3::findSample(int, int*, int*, int*)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:100:3: note: in expansion of macro 'FRN'
  100 |   FRN(i, n) rs = max(rs, confidence[i]);
      |   ^~~
friend.cpp: In function 'void subtask4::dfs(int, int)':
friend.cpp:36:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   36 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
friend.cpp:110:3: note: in expansion of macro 'EACH'
  110 |   EACH(v, adj[u]) {
      |   ^~~~
friend.cpp: In function 'int subtask4::findSample(int, int*, int*, int*)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:120:3: note: in expansion of macro 'FRN'
  120 |   FRN(i, n) subtask4::confidence[i] = confidence[i];
      |   ^~~
friend.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
friend.cpp:121:3: note: in expansion of macro 'FOR'
  121 |   FOR(i, 1, n - 1) {
      |   ^~~
friend.cpp: In function 'void subtask5::bfs(int)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:135:3: note: in expansion of macro 'FRN'
  135 |   FRN(i, n) dis[i] = oo;
      |   ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:142:4: note: in expansion of macro 'FRN'
  142 |    FRN(v, n) {
      |    ^~~
friend.cpp: In function 'int subtask5::findSample(int, int*, int*, int*)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:186:3: note: in expansion of macro 'FRN'
  186 |   FRN(i, n) subtask4::confidence[i] = confidence[i];
      |   ^~~
friend.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
friend.cpp:187:3: note: in expansion of macro 'FOR'
  187 |   FOR(i, 1, n - 1) {
      |   ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:194:5: note: in expansion of macro 'FRN'
  194 |     FRN(j, n)
      |     ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:202:3: note: in expansion of macro 'FRN'
  202 |   FRN(i, n)
      |   ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:205:3: note: in expansion of macro 'FRN'
  205 |   FRN(i, n)
      |   ^~~
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:206:3: note: in expansion of macro 'FRN'
  206 |   FRN(j, n) {
      |   ^~~
friend.cpp: In function 'int solution::findSample(int, int*, int*, int*)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:217:3: note: in expansion of macro 'FRN'
  217 |   FRN(i, n) p[i] = confidence[i];
      |   ^~~
friend.cpp:33:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   33 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
friend.cpp:218:3: note: in expansion of macro 'FOS'
  218 |   FOS(i, n - 1, 1) {
      |   ^~~
friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:34:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   34 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
friend.cpp:239:2: note: in expansion of macro 'FRN'
  239 |  FRN(i, n)
      |  ^~~
friend.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   32 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
friend.cpp:242:2: note: in expansion of macro 'FOR'
  242 |  FOR(i, 1, n - 1) {
      |  ^~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 484 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 476 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 4 ms 3796 KB Output is correct
12 Correct 7 ms 4564 KB Output is correct
13 Correct 4 ms 3412 KB Output is correct
14 Correct 20 ms 7652 KB Output is correct
15 Correct 5 ms 3796 KB Output is correct
16 Correct 6 ms 4056 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 13 ms 6448 KB Output is correct
21 Correct 17 ms 8020 KB Output is correct

Subtask #6
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 24 ms 3480 KB Output is correct
13 Correct 13 ms 1892 KB Output is correct
14 Correct 22 ms 3156 KB Output is correct
15 Correct 21 ms 3076 KB Output is correct