Submission #899452

#	Time	Username	Problem	Language	Result	Execution time	Memory
899452		Nonoze	Training (IOI07_training)	C++17	10 / 100	355 ms	524288 KiB

training

#include<bits/stdc++.h>
#define in long long
#define sz(x) (in)(x.size())
#define f first
#define s second
#define pb push_back
#define z vector
using namespace std;in n=1005,m;z<z<in>>d(n),e(n,z<in>(12)),il(n,z<in>(1<<10,-1)),kk(n,z<in>(n));z<in>f(n);z<z<pair<pair<in,in>,in>>>jj(n);void g(in s,in l=-1){for(auto u:d[s]){if(u==l)continue;f[u]=f[s]+1;e[u][0]=s;for(in i=1;i<12;i++){e[u][i]=e[e[u][i-1]][i-1];}g(u,s);}}in h(in a,in b){if(a==b)return a;if(f[a]<f[b])swap(a,b);in k=f[a]-f[b];for(in j=11;j>=0;j--){if(k&(1<<j)){a=e[a][j];}}if(a==b)return a;for(in j=11;j>=0;j--){if(e[a][j]!=e[b][j]){a=e[a][j];b=e[b][j];}}return e[a][0];}in l(in s,in o){if(il[s][o]!=-1)return il[s][o];in p=0,q=o,r=0;while(q>0){in s=q&(-q);in t=log2(s);for(in i=r;i<t;i++)p+=l(d[s][i],0);r=t+1;q-=s;}for(in i=r;i<sz(d[s]);i++)p+=l(d[s][i],0);for(auto u:jj[s]){in a=u.f.f,b=u.f.s,c=u.s,v=c,w=-1,y=a,bb=b;if(o&kk[a][b])continue;while(a!=s){in x=0;for(in i=0;i<sz(d[a]);i++){if(d[a][i]==w){x+=(1<<i);}}v+=l(a,x);w=a;a=e[a][0];}w=-1;while(b!=s){in x=0;for(in i=0;i<sz(d[b]);i++){if(d[b][i]==w){x+=(1<<i);}}v+=l(b,x);w=b;b=e[b][0];}p=max(p,v+l(s,(o|kk[y][bb])));}return il[s][o]=p;}int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;z<pair<pair<in,in>,in>>r;for(in i=0;i<m;i++){in u,v,c;cin>>u>>v>>c;u--,v--;if(!c){d[u].pb(v);d[v].pb(u);}else{r.pb({{u,v},c});}}f[0]=0;g(0);for(in s=0;s<n;s++) {for(in i=0;i<sz(d[s]);i++){if(d[s][i]==e[s][0]){d[s].erase(d[s].begin()+i);}}}in y=0;for(auto q:r){in u=q.f.f,v=q.f.s,c=q.s,p=h(u,v);if((f[u]+f[v]-2*f[p])%2==0){jj[p].pb({{u,v},c});kk[u][v]=0;for(in j=0;j<sz(d[p]);j++){in s=d[p][j];if(h(s,u)==s||h(s,v)==s){kk[u][v]+=(1<<j);}}}y+=c;}cout<<y-l(0,0);return 0;}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9