제출 #398051

#제출 시각아이디문제언어결과실행 시간메모리
398051ACmachine친구 (IOI14_friend)C++17
0 / 100
10 ms15952 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; } // dinic // so long :( struct flow_edge{ int src, dest; int flow, cap; }; struct flow_network{ vector<vector<int>> g; vector<flow_edge> edges; vector<int> level, ptr; int s, t; int n; int m = 0; int maxF = INF; void add_edge(int u, int v, int cap){ int id = edges.size(); edges.pb({u, v, 0, cap}); edges.pb({u, v, 0, 0}); g[u].pb(m); g[v].pb(m + 1); m += 2; } flow_network(int _n, int _s, int _t) : n(_n), s(_s), t(_t){ g.resize(n); level.resize(n); ptr.resize(n); } bool bfs(){ fill(level.begin(), level.end(), -1); fill(ptr.begin(), ptr.end(), 0); level[s] = 0; queue<int> q; q.push(s); while(!q.empty()){ int v = q.front(); q.pop(); for(int id : g[v]){ auto e = edges[id]; if(e.cap - e.flow < 1 || level[e.dest] != -1) continue; level[e.dest] = level[v] + 1; q.push(e.dest); } } return level[t] != -1; } int dfs(int v, int pushed){ if(pushed == 0) return 0; if(v == t) return pushed; for(int& cid = ptr[v]; cid < g[v].size(); ++cid){ int id = g[v][cid]; auto &e1 = edges[id]; auto &e2 = edges[id^1]; if(level[e1.dest] != level[v] + 1 || e1.cap - e1.flow < 1) continue; int curr_pushed = dfs(e1.dest, min(pushed, e1.cap - e1.flow)); if(curr_pushed == 0) continue; e1.flow += curr_pushed; e2.flow -= curr_pushed; return curr_pushed; } return 0; } int get_flow(){ int res_flow = 0; while(true){ if(!bfs()) break; int pushed; while(true){ int pushed = dfs(s, maxF); res_flow += pushed; if(pushed == 0) break; } } return res_flow; } }; // Find out best sample int findSample(int n,int confidence[],int host[],int protocol[]){ flow_edge a[1000000]; REP(i, 1000000) a[i] = {1, 2, 3 ,4}; REP(i, 1000000){ confidence[i%6] = a[i].cap; } return 5; 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 = [&](){ // smh learn kuhn // 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); } } } delete[]host; delete[]confidence; delete[]protocol; flow_network mf(1005, 1001, 1002); 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; } } } for(int v : curr_visited){ if(dist[v] % 2 == 1) { mf.add_edge(v, mf.t, 1); continue; } mf.add_edge(mf.s, v, 1); for(int x : g[v]){ mf.add_edge(v, x, 1); } } }; REP(i, n){ if(dist[i] == -1){ solve_component(i); } } int max_indep_set = n - mf.get_flow(); return max_indep_set; }; 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 member function 'void flow_network::add_edge(int, int, int)':
friend.cpp:73:13: warning: unused variable 'id' [-Wunused-variable]
   73 |         int id = edges.size();
      |             ^~
friend.cpp: In constructor 'flow_network::flow_network(int, int, int)':
friend.cpp:69:9: warning: 'flow_network::n' will be initialized after [-Wreorder]
   69 |     int n;
      |         ^
friend.cpp:68:9: warning:   'int flow_network::s' [-Wreorder]
   68 |     int s, t;
      |         ^
friend.cpp:80:5: warning:   when initialized here [-Wreorder]
   80 |     flow_network(int _n, int _s, int _t) : n(_n), s(_s), t(_t){
      |     ^~~~~~~~~~~~
friend.cpp: In member function 'int flow_network::dfs(int, int)':
friend.cpp:106:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int& cid = ptr[v]; cid < g[v].size(); ++cid){
      |                                ~~~~^~~~~~~~~~~~~
friend.cpp: In member function 'int flow_network::get_flow()':
friend.cpp:122:17: warning: unused variable 'pushed' [-Wunused-variable]
  122 |             int pushed;
      |                 ^~~~~~
#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...