제출 #607451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
607451		MohamedFaresNebili	Friend (IOI14_friend)	C++14	46 / 100	256 ms	16648 KiB

friend

#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) {
                    set<int> G[N];
                    for(int l = 1; l < N; l++) {
                        int t = protocol[l];
                        if(t == 0)
                            G[host[l]].insert(l),
                            G[l].insert(host[l]);
                        if(t == 1) {
                            for(auto u : G[host[l]])
                                G[u].insert(l),
                                G[l].insert(u);
                        }
                    }
                    vector<int> E; bool vis[N]{0};
                    priority_queue<pair<int, int>,
                    vector<pair<int, int>>, greater<pair<int, int>>> pq;

                    for(int l = 0; l < N; l++)
                        pq.push({G[l].size(), l});

                    while(!pq.empty()) {
                        int A = pq.top().ss; pq.pop();
                        if(vis[A]) continue;
                        E.push_back(A); vis[A] = 1;
                        for(auto u : G[A]) {
                            vis[u] = 1;
                            for(auto v : G[u]) {
                                if(vis[v]) continue;
                                G[v].erase(u);
                                pq.push({G[v].size(), v});
                            }
                        }
                    }
                    return E.size();
                }
            }

컴파일 시 표준 에러 (stderr) 메시지

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:133:13: warning: control reaches end of non-void function [-Wreturn-type]
  133 |             }
      |             ^

• Subtask 1: 11 / 11
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 31