Submission #94949

#TimeUsernameProblemLanguageResultExecution timeMemory
94949Retro3014Training (IOI07_training)C++17
100 / 100
20 ms4816 KiB
#include <iostream> #include <algorithm> #include <vector> #include <stdio.h> #define MAX_N 1000 using namespace std; int N, M; struct S{ int idx, data; }; struct E{ int x, y, z; bool operator <(const E &a)const{ return y<a.y; } }; vector<E> e; vector<int> gp[MAX_N+1]; vector<E> gp2[MAX_N+1]; int p[MAX_N+1][15]; int num[MAX_N+1]; int c[MAX_N+1]; int lv[MAX_N+1]; int ans; int dp[MAX_N+1][(1<<10)]; void dfs(int x){ for(int i=1; i<15; i++){ p[x][i] = p[p[x][i-1]][i-1]; } for(int i=0; i<gp[x].size(); i++){ if(c[gp[x][i]]==0){ num[gp[x][i]] = i; c[gp[x][i]] = 3 - c[x]; p[gp[x][i]][0] = x; lv[gp[x][i]] = lv[x] + 1; dfs(gp[x][i]); } } } int up(int x, int y){ int two = (1<<14); for(int i=14; i>=0; i--){ if(y>=two){ x = p[x][i]; y-=two; } two/=2; } return x; } int lca(int x, int y){ if(lv[x]>lv[y]){ x = up(x, lv[x]-lv[y]); } if(lv[x]<lv[y]){ y = up(y, lv[y]-lv[x]); } if(x==y) return x; for(int i=14; i>=0; i--){ if(p[x][i]!=p[y][i]){ x = p[x][i]; y = p[y][i]; } } if(x==y) return x; return p[x][0]; } int cost(int x, int y){ int ret = 0; int t = 0; while(1){ ret+=dp[x][(1<<10)-1-t]; if(x==y) break; t = (1<<num[x]); x = p[x][0]; } return ret; } void dfs2(int x){ for(int i=0; i<gp[x].size(); i++){ if(gp[x][i]!=p[x][0]){ dfs2(gp[x][i]); } } for(int i=0; i<gp2[x].size(); i++){ int pp1, pp2; E now = gp2[x][i]; pp1 = up(now.x, lv[now.x]-lv[x]-1); pp2 = up(now.y, lv[now.y]-lv[x]-1); if(now.x==x) now.z+=cost(now.y, pp2); else if(now.y==x) now.z+=cost(now.x, pp1); else now.z+=cost(now.y, pp2)+cost(now.x, pp1); for(int j=0; j<gp[x].size(); j++){ if(pp1==gp[x][j]) now.x = j; if(pp2==gp[x][j]) now.y = j; } if(pp1==x) now.x = -1; if(pp2==x) now.y = -1; if(now.x>now.y) {int tmp = now.x; now.x = now.y; now.y = tmp;} gp2[x][i] = now; } sort(gp2[x].begin(), gp2[x].end()); for(int i=0; i<(1<<10); i++) dp[x][i] = 0; for(int i=0; i<gp[x].size(); i++){ if(gp[x][i]==p[x][0]) continue; for(int j=0; j<(1<<10); j++){ if(((1<<i)&j)==0) continue; dp[x][j] += dp[gp[x][i]][(1<<10)-1]; } } for(int i=0; i<gp2[x].size(); i++){ E now = gp2[x][i]; if(now.x==-1){ for(int j=0; j<(1<<10); j++){ if((j&(1<<now.y))!=0) continue; dp[x][j+(1<<now.y)] = max(dp[x][j+(1<<now.y)], dp[x][j]+now.z); } }else{ for(int j=0; j<(1<<10); j++){ if((j&(1<<now.x))!=0) continue; if((j&(1<<now.y))!=0) continue; dp[x][j+(1<<now.y)+(1<<now.x)] = max(dp[x][j+(1<<now.y)+(1<<now.x)], dp[x][j]+now.z); } } } return; } int degree[MAX_N+1]; int main(){ scanf("%d%d", &N, &M); for(int i=0; i<M; i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); if(c==0){ degree[a]++; degree[b]++; gp[a].push_back(b); gp[b].push_back(a); }else{ e.push_back({a, b, c}); ans+=c; } } int now=1; c[now] = 1; lv[now] = 1; dfs(now); for(int i=0; i<e.size(); i++){ if(c[e[i].x]==c[e[i].y]){ gp2[lca(e[i].x, e[i].y)].push_back(e[i]); } } dfs2(now); ans-=dp[now][(1<<10)-1]; printf("%d", ans); return 0; }

Compilation message (stderr)

training.cpp: In function 'void dfs(int)':
training.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
training.cpp: In function 'void dfs2(int)':
training.cpp:91:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
training.cpp:96:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp2[x].size(); i++){
               ~^~~~~~~~~~~~~~
training.cpp:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[x].size(); j++){
                ~^~~~~~~~~~~~~
training.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
training.cpp:121:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp2[x].size(); i++){
               ~^~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:159:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<e.size(); i++){
               ~^~~~~~~~~
training.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
training.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...
#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...