Submission #545960

#TimeUsernameProblemLanguageResultExecution timeMemory
545960stefantagaTraining (IOI07_training)C++14
20 / 100
15 ms13152 KiB
#include <bits/stdc++.h> using namespace std; struct NonTreeEdge { int x,y,cost; }; vector <NonTreeEdge> salut; vector <int> arb[8005]; int niv[8005]; int fiu[8005],tata[8005]; int rmqTree[8005][14],q,prim[8005]; vector <int> fii[8005]; void dfs(int x,int dad) { int nr=0; niv[x]=niv[dad]+1; rmqTree[++q][0]=x; prim[x]=q; for (int i=0;i<arb[x].size();i++) { int nod = arb[x][i]; if (nod!=dad) { tata[nod]=x; dfs(nod,x); fii[x].push_back(nod); fiu[nod]=nr; nr++; rmqTree[++q][0]=x; } } } int n; int din[1005][5005]; int i,j,m; vector <NonTreeEdge> mn[1005]; int lca(int x,int y) { if (x==y) { return x; } x=prim[x]; y=prim[y]; if (x>y) { swap(x,y); } int dif = y-x; int k =log2(dif); if (niv[rmqTree[x][k]]<niv[rmqTree[y-(1<<k)+1][k]]) { return rmqTree[x][k]; } return rmqTree[y-(1<<k)+1][k]; } int rasp (int rad, int mask) { if (din[rad][mask]!=-1) { return din[rad][mask]; } int raspfv=0,p=1,nr=0; for (int i=0;i<fii[rad].size();i++) { if ((mask&(1<<i))) { continue; } raspfv= raspfv + rasp(fii[rad][i],0); } din[rad][mask]=raspfv; for (int i=0;i<mn[rad].size();i++) { int x=mn[rad][i].x; int y=mn[rad][i].y; int cost = mn[rad][i].cost; int varf = lca(x,y); int copx=x,cop=y; int p=1,ok=1; for (int j=0;j<fii[rad].size();j++) { if (mask&p) { if (lca(x,fii[rad][j])==fii[rad][j]||lca(y,fii[rad][j])==fii[rad][j]) { ok=0; break; } } p=p*2; } if (ok==0) { continue; } int sum=0; varf = lca(x,y); if (y==varf) { swap(x,y); } if (x==varf) { sum=sum+rasp(y,0)+cost; cop=y; while (cop!=x) { sum=sum+rasp(tata[cop],(1<<fiu[cop])); cop=tata[cop]; } } else { sum=sum+rasp(y,0)+rasp(x,0)+cost; cop=y; while (tata[cop]!=varf) { sum=sum+rasp(tata[cop],(1<<fiu[cop])); cop=tata[cop]; } copx=x; while (tata[copx]!=varf) { sum=sum+rasp(tata[copx],(1<<fiu[copx])); copx=tata[copx]; } sum=sum+rasp(varf,(1<<fiu[copx])+(1<<fiu[cop])); } din[rad][mask]=max(din[rad][mask],sum); } return din[rad][mask]; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>n>>m; int lastv=0; for (int i=1;i<=m;i++) { int x,y,tip; cin>>x>>y>>tip; if (tip==0) { arb[x].push_back(y); arb[y].push_back(x); } else { salut.push_back({x,y,tip}); lastv+=tip; } } dfs(1,0); int lg = log2(q); int p = 1; for (int j=1;j<=lg;j++) { for (i=1;i<=q;i++) { if (niv[rmqTree[i][j-1]]<niv[rmqTree[i+p][j-1]]) { rmqTree[i][j]=rmqTree[i][j-1]; } else { rmqTree[i][j]=rmqTree[i+p][j-1]; } } p=p*2; } int lim = (1<<11); for (i=1;i<=n;i++) { for (j=0;j<lim;j++) { din[i][j]=-1; } } for (i=0;i<salut.size();i++) { int x= salut[i].x; int y = salut[i].y; int ceau =lca (salut[i].x,salut[i].y); if ((niv[salut[i].x]+niv[salut[i].y]-2*niv[ceau])%2==1) { continue; } mn[ceau].push_back(salut[i]); } cout<<lastv-rasp(1,0); return 0; }

Compilation message (stderr)

training.cpp: In function 'void dfs(int, int)':
training.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i=0;i<arb[x].size();i++)
      |                  ~^~~~~~~~~~~~~~
training.cpp: In function 'int rasp(int, int)':
training.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i=0;i<fii[rad].size();i++)
      |                  ~^~~~~~~~~~~~~~~~
training.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i=0;i<mn[rad].size();i++)
      |                  ~^~~~~~~~~~~~~~~
training.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int j=0;j<fii[rad].size();j++)
      |                      ~^~~~~~~~~~~~~~~~
training.cpp:64:18: warning: unused variable 'p' [-Wunused-variable]
   64 |     int raspfv=0,p=1,nr=0;
      |                  ^
training.cpp:64:22: warning: unused variable 'nr' [-Wunused-variable]
   64 |     int raspfv=0,p=1,nr=0;
      |                      ^~
training.cpp: In function 'int main()':
training.cpp:186:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<NonTreeEdge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for (i=0;i<salut.size();i++)
      |              ~^~~~~~~~~~~~~
training.cpp:188:13: warning: unused variable 'x' [-Wunused-variable]
  188 |         int x= salut[i].x;
      |             ^
training.cpp:189:13: warning: unused variable 'y' [-Wunused-variable]
  189 |         int y = salut[i].y;
      |             ^
#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...