| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 899452 |
2024-01-06T08:12:20 Z |
Nonoze |
Training (IOI07_training) |
C++17 |
|
300 ms |
524288 KB |
#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;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16472 KB |
Output is correct |
| 2 |
Correct |
7 ms |
16476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
16476 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
16624 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
355 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
283 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
292 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
281 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
294 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
301 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
33732 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
34128 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
