| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 607442 | MohamedFaresNebili | Friend (IOI14_friend) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int MOD = 998244353;
int par[1001], res[1001], DP[1001][2];
vector<int> adj[1001];
int findSet(int v) {
if(par[v] == v) return v;
return par[v] = findSet(par[v]);
}
void unionSet(int u, int v) {
u = findSet(u), v = findSet(v);
if(u == v) return;
par[u] = v; res[v] = max(res[v], res[u]);
}
int dfs(int v, int p, int state, int* confidence) {
if(DP[v][state] != -1) return DP[v][state];
int A = 0, B = confidence[v];
for(auto u : adj[v]) {
if(u == p) continue;
A += dfs(u, v, 0, confidence);
B += dfs(u, v, 1, confidence);
}
if(state) B = 0;
return DP[v][state] = max(A, B);
}
int findSample(int N, int* confidence,
int* host, int* protocol) {
bool S1 = 1, S2 = 1, S3 = 1, S4 = 1, S5 = 1;
for(int l = 1; l < N; l++)
S1 &= (protocol[l] == 0),
S2 &= (protocol[l] == 1),
S3 &= (protocol[l] == 2),
S5 &= (confidence[l] == 1);
S4 &= (N <= 10); S5 &= (confidence[0] == 1);
if(S1) {
memset(DP, -1, sizeof DP);
for(int l = 1; l < N; l++)
adj[host[l]].push_back(l),
adj[l].push_back(host[l]);
return dfs(0, 0, 0, confidence);
}
if(S2 || S3) {
for(int l = 0; l < N; l++)
par[l] = l, res[l] = confidence[l];
for(int l = 1; l < N; l++) {
if(protocol[l] < 2) continue;
unionSet(l, host[l]);
}
int ans = 0;
for(int l = 0; l < N; l++) {
if(par[l] != l) continue;
ans += res[l];
}
return ans;
}
if(S4) {
vector<int> perm; int best = 0;
for(int l = 0; l < N; l++)
perm.push_back(l);
for(int l = 1; l < N; l++) {
int t = protocol[l];
if(t != 1)
adj[host[l]].push_back(l),
adj[l].push_back(host[l]);
if(t != 0) {
for(auto u : adj[host[l]])
adj[u].push_back(l),
adj[l].push_back(u);
}
}
do{
bool vis[N]{0}; int ans = 0;
for(int l = 0; l < N; l++) {
if(vis[perm[l]]) continue;
ans += confidence[perm[l]];
for(auto u : adj[perm[l]]) vis[u] = 1;
}
best = max(best, ans);
} while(next_permutation(perm.begin(), perm.end()));
return best;
}
if(S5) {
for(int l = 1; l < N; l++) {
int t = protocol[l];
if(t == 0)
adj[host[l]].push_back(l),
adj[l].push_back(host[l]);
if(t == 1) {
for(auto u : adj[host[l]])
adj[u].push_back(l),
adj[l].push_back(u);
}
}
int best = 0; srand(7892);
for(int _ = 0; _ < 100000; _++) {
vector<int> E, W; bool vis[N]{0};
for(int l = 0; l < N; l++) W.push_back(l);
random_shuffle(W.begin(), W.end());
while(!W.empty()) {
int A = W.back(); W.pop_back();
if(vis[A]) continue;
E.push_back(A);
for(auto u : adj[A])
vis[u] = 1;
}
best = max(best, (int)E.size());
}
return best;
}