Submission #94925

#TimeUsernameProblemLanguageResultExecution timeMemory
94925Retro3014Training (IOI07_training)C++17
30 / 100
24 ms632 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 c[MAX_N+1]; int lv[MAX_N+1]; int ans; int dp[MAX_N+1]; 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){ 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]; } vector<int> dp2(2000, 0); void dfs2(int x){ dp[x] = 0; 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+=dp[now.y]; else if(now.y==x) now.z+=dp[now.x]; else now.z+=dp[now.x]+dp[now.y]; 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<2000; i++){ dp2[i] = 0; } for(int i=0; i<gp[x].size(); i++){ if(gp[x][i]==p[x][0]) continue; for(int j=0; j<dp2.size(); j++){ if(((1<<i)&j)==0) continue; dp2[j] += dp[gp[x][i]]; } } for(int i=0; i<gp2[x].size(); i++){ E now = gp2[x][i]; if(now.x==-1){ for(int j=0; j<dp2.size(); j++){ if((j&(1<<now.y))!=0) continue; if(j+(1<<now.y)>=2000) continue; dp2[j+(1<<now.y)] = max(dp2[j+(1<<now.y)], dp2[j]+now.z); } }else{ for(int j=0; j<dp2.size(); j++){ if((j&(1<<now.x))!=0) continue; if((j&(1<<now.y))!=0) continue; if(j+(1<<now.y)+(1<<now.x)>=2000) continue; dp2[j+(1<<now.y)+(1<<now.x)] = max(dp2[j+(1<<now.y)+(1<<now.x)], dp2[j]+now.z); } } } for(int i=0; i<2000; i++) dp[x] = max(dp[x], dp2[i]); 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]; printf("%d", ans); return 0; }

Compilation message (stderr)

training.cpp: In function 'void dfs(int)':
training.cpp:36: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:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
training.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp2[x].size(); i++){
               ~^~~~~~~~~~~~~~
training.cpp:91:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[x].size(); j++){
                ~^~~~~~~~~~~~~
training.cpp:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
training.cpp:106:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<dp2.size(); j++){
                ~^~~~~~~~~~~
training.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp2[x].size(); i++){
               ~^~~~~~~~~~~~~~
training.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<dp2.size(); j++){
                 ~^~~~~~~~~~~
training.cpp:120:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<dp2.size(); j++){
                 ~^~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:152:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<e.size(); i++){
               ~^~~~~~~~~
training.cpp:135: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:139: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...