제출 #398071

#제출 시각아이디문제언어결과실행 시간메모리
398071ACmachine친구 (IOI14_friend)C++17
46 / 100
267 ms65540 KiB
#include "friend.h" #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in) #define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in) #define REP(i,b) FOR(i,0,b,1) #define REPD(i,b) FORD(i,b,0,1) #define pb push_back #define mp make_pair #define ff first #define ss second #define all(x) begin(x), end(x) #define MANY_TESTS int tcase; cin >> tcase; while(tcase--) const double EPS = 1e-9; const int MOD = 1e9+7; const ll INFF = 1e18; const int INF = 1e9; const ld PI = acos((ld)-1); const vi dy = {1, 0, -1, 0, -1, 1, 1, -1}; const vi dx = {0, 1, 0, -1, -1, 1, -1, 1}; void DBG(){cout << "]" << endl;} template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); } #define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__); #define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl; template<class T, unsigned int U> ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;} template <class T, class U> ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;} template <class T> ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template <class T, class U> ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template<class T> ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;} template<class T> istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; } // Find out best sample int findSample(int n,int confidence[],int host[],int protocol[]){ auto solve_1 = [&](){ vector<vector<int>> mat(n, vector<int>(n, 0)); vector<vector<int>> g(n); auto join = [&](int u, int v){ g[u].pb(v); g[v].pb(u); mat[u][v] = mat[v][u] = 1; }; FOR(i, 1, n, 1){ if(protocol[i] == 0){ join(host[i], i); } else if(protocol[i] == 1){ for(int x : g[host[i]]){ join(x, i); } } else{ for(int x : g[host[i]]){ join(x, i); } join(host[i], i); } } int ans = 0; REP(i, (1 << n)){ bool can = true; int tm = 0; REP(j, n){ if(i&(1 << j)){ tm += confidence[j]; } } REP(j, n){ REP(k, n){ if(j == k) continue; if((i&(1 << j)) && (i&(1 << k))){ if(mat[j][k]) can = false; } } } if(can) ans = max(ans, tm); } return ans; }; auto solve_subtask_2 = [&](){ int ans = 0; REP(i, n) ans += confidence[i]; return ans; }; auto solve_subtask_3 = [&](){ int ans = 0; REP(i, n) ans = max(ans, confidence[i]); return ans; }; auto solve_subtask_4 = [&](){ vector<vector<int>> g(n); FOR(i, 1, n, 1){ g[host[i]].pb(i); g[i].pb(host[i]); } vector<array<int, 2>> dp(n, {0, 0}); function<void(int, int)> dfs = [&](int v, int p){ for(int x : g[v]){ if(x == p) continue; dfs(x, v); } dp[v][1] = confidence[v]; for(int x : g[v]){ if(x == p) continue; dp[v][1] += dp[x][0]; dp[v][0] += max(dp[x][1], dp[x][0]); } }; dfs(0, -1); return max(dp[0][0], dp[0][1]); }; auto solve_subtask_5 = [&](){ // always bipartite // max indep set = n - max matching vector<vector<int>> g(n); FOR(i, 1, n, 1){ if(protocol[i] == 0){ g[i].pb(host[i]); g[host[i]].pb(i); } else{ for(int x : g[host[i]]){ g[x].pb(i); g[i].pb(x); } } } vector<vector<int>> ng(n); vector<int> dist(n, -1); auto solve_component = [&](int s){ queue<int> q; dist[s] = 0; q.push(s); vector<int> curr_visited; while(!q.empty()){ int v = q.front(); curr_visited.pb(v); q.pop(); for(int x : g[v]){ if(dist[x] == -1){ dist[x] = dist[v] + 1; q.push(x); } } } for(int v : curr_visited){ if(dist[v] % 2 == 1) { continue; } for(int x : g[v]){ ng[v].pb(x); } } }; REP(i, n){ if(dist[i] == -1) solve_component(i); } vector<bool> visited(n, false); vector<int> matched(n, -1); function<bool(int)> dfs = [&](int v){ if(visited[v]) return false; visited[v] = true; for(int x : ng[v]){ if(matched[x] == -1 || dfs(matched[x])){ matched[x] = v; return true; } } return false; }; int matching = 0; REP(i, n){ dbg(i) if(dist[i] % 2 == 0){ fill(all(visited), false); if(dfs(i)) matching++; } } return n - matching; }; bool sub2 = true; FOR(i, 1, n, 1){ if(protocol[i] != 1) sub2 = false; } bool sub3 = true; FOR(i, 1, n, 1){ if(protocol[i] != 2) sub3 = false; } bool sub4 = true; FOR(i, 1, n, 1){ if(protocol[i] != 0) sub4 = false; } if(n <= 10) return solve_1(); else if(sub2) return solve_subtask_2(); else if(sub3) return solve_subtask_3(); else if(sub4) return solve_subtask_4(); else solve_subtask_5(); //return ans; }

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

friend.cpp: In function 'int findSample(int, int*, int*, int*)':
friend.cpp:232:1: warning: control reaches end of non-void function [-Wreturn-type]
  232 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...