제출 #295676

#제출 시각아이디문제언어결과실행 시간메모리
295676stoyan_malinin친구 (IOI14_friend)C++14
0 / 100
2 ms1024 KiB
#include "friend.h" //#include "grader.cpp" #include <queue> #include <vector> #include <cstring> #include <iostream> using namespace std; const int MAXN = 1015; int n; vector <int> graph[MAXN]; void constructGrahp(int n, int confidence[], int host[], int protocol[]) { for(int x = 1;x<=n;x++) { if(protocol[x]==0) { graph[ host[x] ].push_back(x); graph[x].push_back(host[x]); } else if(protocol[x]==1) { for(int y: graph[ host[x] ]) { graph[y].push_back(x); graph[x].push_back(y); } } else if(protocol[x]==2) { graph[x].push_back(host[x]); graph[ host[x] ].push_back(x); for(int y: graph[ host[x] ]) { graph[y].push_back(x); graph[x].push_back(y); } } } } namespace Subtask1 { bool can(int x, int mask) { for(int y: graph[x]) { if(((mask>>y)&1)==1) return false; } return true; } int rec(int x, int mask, int confidence[]) { if(x==n) return 0; int answer = rec(x+1, mask, confidence); if(can(x, mask)==true) answer = max(answer, confidence[x]+rec(x+1, (mask|(1<<x)), confidence)); return answer; } int solve(int n, int confidence[], int host[], int protocol[]) { constructGrahp(n, confidence, host, protocol); return rec(0, 0, confidence); } }; namespace Subtask2 { int solve(int n, int confidence[], int host[], int protocol[]) { int ans = 0; for(int x = 0;x<n;x++) ans += confidence[x]; return ans; } }; namespace Subtask3 { int solve(int n, int confidence[], int host[], int protocol[]) { int ans = 0; for(int x = 0;x<n;x++) ans = max(ans, confidence[x]); return ans; } }; namespace Subtask4 { int memo[MAXN][2]; int rec(int x, int last, bool take, int confidence[]) { if(memo[x][take]!=-1) return memo[x][take]; int answer = 0; if(take==true) { answer += confidence[x]; for(int y: graph[x]) { if(y==last) continue; answer += rec(y, x, false, confidence); } } else { for(int y: graph[x]) { if(y==last) continue; answer += max(rec(y, x, true, confidence), rec(y, x, false, confidence)); } } memo[x][take] = answer; return answer; } int solve(int n, int confidence[], int host[], int protocol[]) { memset(memo, -1, sizeof(memo)); constructGrahp(n, confidence, host, protocol); return max(rec(0, -1, false, confidence), rec(0, -1, true, confidence)); } }; namespace Subtask5 { struct MaxFlowGraph { int S, T; int dist[MAXN], ind[MAXN]; vector <int> edges; vector <pair <int, int>> graph[MAXN]; MaxFlowGraph(){} MaxFlowGraph(int S, int T) { this->S = S; this->T = T; } void addEdge(int u, int v, int cap) { //cout << u << " -> " << v << '\n'; graph[u].push_back({v, edges.size()}); edges.push_back(cap); graph[v].push_back({u, edges.size()}); edges.push_back(0); } void bfs(int x) { memset(dist, -1, sizeof(dist)); queue <int> q; dist[x] = 0; q.push(x); while(q.empty()==false) { x = q.front(); q.pop(); for(pair <int, int> y: graph[x]) { if(dist[y.first]==-1 && edges[y.second]>0) { dist[y.first] = dist[x] + 1; q.push(y.first); } } } } int dfs(int x, int minEdge) { if(x==T) return minEdge; for(int i = ind[x];i<graph[x].size();i++) { if(dist[ graph[x][i].first ]==dist[x]+1 && edges[ graph[x][i].second ]>0) { int flow = dfs(graph[x][i].first, min(minEdge, edges[ graph[x][i].second ])); if(flow!=-1) { edges[ graph[x][i].second ] -= flow; edges[ graph[x][i].second^1 ] += flow; return flow; } } //ind[x]++; } return -1; } int Dinic() { int flow = 0; while(true) { bfs(S); if(dist[T]==-1) break; memset(ind, 0, sizeof(ind)); while(true) { int add = dfs(S, 1); if(add==-1) break; flow += add; } } return flow; } }; int color[MAXN]; void dfsColor(int x, int col, MaxFlowGraph &G) { color[x] = col + 1; for(int y: graph[x]) { if(color[y]==0) { dfsColor(y, col^1, G); } } } int solve(int n, int confidence[], int host[], int protocol[]) { constructGrahp(n, confidence, host, protocol); int S = n, T = n + 1; MaxFlowGraph G(S, T); vector <pair <int, int>> all; for(int x = 1;x<n;x++) { if(protocol[x]==0) { all.push_back({host[x], x}); //G.addEdge(host[x], x, 1); } else { for(pair <int, int> y: G.graph[ host[x] ]) { all.push_back({y.first, x}); //G.addEdge(y.first, x, 1); } } } for(int x = 0;x<n;x++) { if(color[x]==0) dfsColor(x, 0, G); } for(pair <int, int> x: all) { int u = x.first; int v = x.second; if(color[u]>color[v]) swap(u, v); G.addEdge(u, v, 1); } for(int x = 0;x<n;x++) { if(color[x]==1) G.addEdge(S, x, 1); else G.addEdge(x, T, 1); } //cout << "K" << '\n'; return n - G.Dinic(); } }; int guessSubtask(int n, int confidence[], int host[], int protocol[]) { if(n<=10) return 1; bool subtask2 = true; for(int x = 1;x<n;x++) { if(protocol[x]!=1) { subtask2 = false; break; } } if(subtask2==true) return 2; bool subtask3 = true; for(int x = 1;x<n;x++) { if(protocol[x]!=2) { subtask3 = false; break; } } if(subtask3==true) return 3; bool subtask4 = true; for(int x = 1;x<n;x++) { if(protocol[x]!=0) { subtask4 = false; break; } } if(subtask4==true) return 4; bool subtask5 = true; for(int x = 1;x<n;x++) { if(protocol[x]==2) { subtask5 = false; break; } } if(subtask5==true) return 5; return -1; } int findSample(int _n,int confidence[],int host[],int protocol[]) { n = _n; int subtask = 5;//guessSubtask(n, confidence, host, protocol); if(subtask==2) return Subtask2::solve(n, confidence, host, protocol); if(subtask==3) return Subtask3::solve(n, confidence, host, protocol); if(subtask==1) return Subtask1::solve(n, confidence, host, protocol); if(subtask==4) return Subtask4::solve(n, confidence, host, protocol); if(subtask==5) return Subtask5::solve(n, confidence, host, protocol); return 0; }

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

friend.cpp: In member function 'int Subtask5::MaxFlowGraph::dfs(int, int)':
friend.cpp:196:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |             for(int i = ind[x];i<graph[x].size();i++)
      |                                ~^~~~~~~~~~~~~~~~
#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...