Submission #697270

#TimeUsernameProblemLanguageResultExecution timeMemory
697270vjudge1Training (IOI07_training)C++14
100 / 100
13 ms4644 KiB
#include<bits/stdc++.h> #define ll long long #define lll __int128 #define db double #define ld long double #define pii pair<int,int> #define fi first #define se second #define vi vector<int> using namespace std; namespace IO { const int SZ=1<<20; char gchar() { static char buf[SZ]; static int i=SZ; if(i==SZ)i=0,fread(buf,1,SZ,stdin); return buf[i++]; } void pchar(char c) { static char buf[SZ]; static int i=0; if(c)buf[i++]=c; if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0; } void pstr(string s,char end='\n') { for(char c:s)pchar(c); pchar(end); } template<typename T>void read(T &x) { x=0;int f=1; static char c; while((c=gchar())>'9'||c<'0')if(c=='-')f=-1; x=c-'0'; while((c=gchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48); x*=f; } template<typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);} template<typename T>void i_write(T x) { if(x>9)i_write(x/10); pchar(x%10+'0'); } template<typename T>void write(T x,char end='\n') { if(x<0)pchar('-'),x=-x; if(x>9)i_write(x/10); pchar(x%10+'0'); pchar(end); } } using IO::read; using IO::write; const int N=1010; int n,m,ans; vector<int>e[N]; struct node { int src,des,val; }; vector<node>vec,link[N]; int dep[N],fa[N],siz[N],wson[N],top[N],fid[N]; int f[N][1<<10]; void dfs1(int u,int f) { fa[u]=f,siz[u]=1,dep[u]=dep[f]+1; for(int v:e[u]) { if(v==f)continue; dfs1(v,u),siz[u]+=siz[v]; if(siz[v]>siz[wson[u]])wson[u]=v; } } void dfs2(int u,int t) { top[u]=t; if(wson[u])dfs2(wson[u],t); for(int v:e[u]) if(v!=wson[u]&&v!=fa[u])dfs2(v,v); } void dfs3(int u) { for(int i=0;i<(int)e[u].size();i++) { int v=e[u][i]; if(v==fa[u])continue; fid[v]=1<<i,dfs3(v); } } int lca(int u,int v) { while(top[u]!=top[v]) { if(dep[top[u]]<dep[top[v]])swap(u,v); u=fa[top[u]]; } return dep[u]>dep[v]?v:u; } void dfs(int u) { for(int v:e[u]) if(v!=fa[u])dfs(v); int cnt=e[u].size(); for(int msk=0;msk<(1<<cnt);msk++) for(int i=0;i<cnt;i++) if(!(msk&(1<<i)))f[u][msk]+=f[e[u][i]][0]; for(auto e:link[u]) { int val=e.val,x=0,y=0; if(e.src!=u) { val+=f[e.src][0]; for(x=e.src;fa[x]!=u;x=fa[x]) val+=f[fa[x]][fid[x]]; } if(e.des!=u) { val+=f[e.des][0]; for(y=e.des;fa[y]!=u;y=fa[y]) val+=f[fa[y]][fid[y]]; } int s=fid[x]|fid[y]; for(int msk=0;msk<(1<<cnt);msk++) if(!(msk&s))f[u][msk]=max(f[u][msk],val+f[u][msk|s]); } } int main() { read(n,m); for(int i=1,u,v,w;i<=m;i++) { read(u,v,w); if(!w)e[u].push_back(v),e[v].push_back(u); else ans+=w,vec.push_back((node){u,v,w}); } dfs1(1,0),dfs2(1,1),dfs3(1); for(auto e:vec) { int x=lca(e.src,e.des); if(!((dep[e.src]+dep[e.des]-dep[x]*2)&1)) link[x].push_back(e); } dfs(1); printf("%d",ans-f[1][0]); return 0; }

Compilation message (stderr)

training.cpp: In function 'char IO::gchar()':
training.cpp:18:24: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |      if(i==SZ)i=0,fread(buf,1,SZ,stdin);
      |                   ~~~~~^~~~~~~~~~~~~~~~
#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...