oj.uz

답안 #899452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899452 2024-01-06T08:12:20 Z Nonoze Training (IOI07_training) C++17
10 / 100
 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;}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 16472 KB Output is correct
2 Correct 7 ms 16476 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 16728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 355 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 283 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 292 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 281 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 294 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 301 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 33732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 34128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -