Submission #691897
Source Code Expand
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <vector> #include <set> #include <queue> #define SIZE 100005 using namespace std; typedef long long int ll; typedef pair <int,int> P; typedef pair <int,P> PP; struct UF { int par[SIZE],rank[SIZE]; void init(int n) { for(int i=0;i<n;i++) { par[i]=i; rank[i]=0; } } int find(int x) { if(par[x]==x) return x; return par[x]=find(par[x]); } void unite(int x,int y)//x->y { x=find(x); y=find(y); if(x==y) return; par[x]=y; } }; UF left,right; //O(n*log^2n) priority_queue <int,vector <int>, greater <int> > que[SIZE]; set <PP> mn; set <PP>::iterator it; bool use[SIZE]; int n; void remL(int k) { if(k>0) { int l=left.find(k-1); mn.erase(PP(que[k].top()+que[l].top(),P(l,k))); } } void remR(int k) { int r=right.find(k)+1; if(r<n) mn.erase(PP(que[k].top()+que[r].top(),P(k,r))); } void remT(int k) { if(que[k].size()>=2) { int s=que[k].top();que[k].pop(); mn.erase(PP(s+que[k].top(),P(k,k))); que[k].push(s); } } void remX(int k) { if(!use[k]||k==0) return; int l=left.find(k-1); int r=right.find(k)+1; if(r<n) mn.erase(PP(que[l].top()+que[r].top(),P(l,r))); } void rem(int k) { remL(k),remR(k),remT(k),remX(k); } void insL(int k) { if(k>0) { int l=left.find(k-1); mn.insert(PP(que[k].top()+que[l].top(),P(l,k))); } } void insR(int k) { int r=right.find(k)+1; if(r<n) mn.insert(PP(que[k].top()+que[r].top(),P(k,r))); } void insT(int k) { if(que[k].size()>=2) { int s=que[k].top();que[k].pop(); mn.insert(PP(s+que[k].top(),P(k,k))); que[k].push(s); } } void insX(int k) { if(!use[k]||k==0) return; int l=left.find(k-1); int r=right.find(k)+1; if(r<n) mn.insert(PP(que[l].top()+que[r].top(),P(l,r))); } void merge(int l,int r)//l<-r { if(que[l].size()<que[r].size()) swap(que[l],que[r]); while(!que[r].empty()) { que[l].push(que[r].top()); que[r].pop(); } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { int a; scanf("%d",&a); que[i].push(a); } left.init(n+2); right.init(n+2); for(int i=0;i+1<n;i++) insR(i); ll ret=0; for(int i=0;i+1<n;i++) { it=mn.begin(); PP p=*it;mn.erase(it); ret+=p.first; int l=p.second.first,r=p.second.second; rem(l),rem(r); //printf("%d %d : %d\n",l,r,p.first); if(l==r) { que[l].pop();que[l].pop(); que[l].push(p.first); insL(l); insR(l); insT(l); insX(l); } else { int m=-1,x=-1,y=-1; if(right.find(l)+1!=r) { m=right.find(l)+1; rem(m); } y=right.find(r)+1; if(y<n&&use[y]) rem(y); else y=-1; if(l>0) { x=left.find(l-1); if(use[x]) rem(x); else x=-1; } //printf("* %d %d %d\n",m,x,y); left.unite(r,l); right.unite(l,r); que[l].pop();que[r].pop();merge(l,r); que[l].push(p.first); if(m!=-1) { left.unite(m,l); right.unite(m,r); merge(l,m); } if(y!=-1) { left.unite(y,l); right.unite(l,y); merge(l,y); } if(x!=-1) { left.unite(l,x); right.unite(x,l); merge(x,l); l=x; } use[l]=true; insL(l); insR(l); insT(l); insX(l); } //printf("[%d %d]\n",left.find(l),right.find(l));puts(""); } printf("%lld\n",ret); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 最適二分探索木 |
User | yutaka1999 |
Language | C++14 (GCC 5.4.1) |
Score | 101 |
Code Size | 3449 Byte |
Status | AC |
Exec Time | 511 ms |
Memory | 14720 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:122:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:126:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&a); ^
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
Dataset1 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt |
Dataset2 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt |
Dataset3 | 00_sample_01.txt, 01_00.txt, 01_01.txt, 01_02.txt, 01_03.txt, 01_04.txt, 01_05.txt, 01_06.txt, 01_07.txt, 01_08.txt, 01_09.txt, 01_10.txt, 01_11.txt, 01_12.txt, 01_13.txt, 01_14.txt, 01_15.txt, 01_16.txt, 01_17.txt, 01_18.txt, 01_19.txt, 01_20.txt, 01_21.txt, 01_22.txt, 01_23.txt, 01_24.txt, 01_25.txt, 01_26.txt, 01_27.txt, 01_28.txt, 01_29.txt, 02_00.txt, 02_01.txt, 02_02.txt, 02_03.txt, 02_04.txt, 02_05.txt, 02_06.txt, 02_07.txt, 02_08.txt, 02_09.txt, 02_10.txt, 02_11.txt, 02_12.txt, 02_13.txt, 02_14.txt, 02_15.txt, 02_16.txt, 02_17.txt, 02_18.txt, 02_19.txt, 02_20.txt, 02_21.txt, 02_22.txt, 02_23.txt, 02_24.txt, 02_25.txt, 02_26.txt, 02_27.txt, 02_28.txt, 02_29.txt, 03_00.txt, 03_01.txt, 03_02.txt, 03_03.txt, 03_04.txt, 03_05.txt, 03_06.txt, 03_07.txt, 03_08.txt, 03_09.txt, 03_10.txt, 03_11.txt, 03_12.txt, 03_13.txt, 03_14.txt, 03_15.txt, 03_16.txt, 03_17.txt, 03_18.txt, 03_19.txt, 03_20.txt, 03_21.txt, 03_22.txt, 03_23.txt, 03_24.txt, 03_25.txt, 03_26.txt, 03_27.txt, 03_28.txt, 03_29.txt, 03_30.txt, 03_31.txt, 03_32.txt, 03_33.txt, 03_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 8 ms | 3328 KB |
01_00.txt | AC | 8 ms | 3328 KB |
01_01.txt | AC | 8 ms | 3328 KB |
01_02.txt | AC | 8 ms | 3328 KB |
01_03.txt | AC | 8 ms | 3328 KB |
01_04.txt | AC | 8 ms | 3328 KB |
01_05.txt | AC | 11 ms | 3328 KB |
01_06.txt | AC | 8 ms | 3328 KB |
01_07.txt | AC | 8 ms | 3328 KB |
01_08.txt | AC | 8 ms | 3328 KB |
01_09.txt | AC | 8 ms | 3328 KB |
01_10.txt | AC | 8 ms | 3328 KB |
01_11.txt | AC | 8 ms | 3328 KB |
01_12.txt | AC | 8 ms | 3328 KB |
01_13.txt | AC | 8 ms | 3328 KB |
01_14.txt | AC | 8 ms | 3328 KB |
01_15.txt | AC | 8 ms | 3328 KB |
01_16.txt | AC | 8 ms | 3328 KB |
01_17.txt | AC | 8 ms | 3328 KB |
01_18.txt | AC | 8 ms | 3328 KB |
01_19.txt | AC | 9 ms | 3328 KB |
01_20.txt | AC | 8 ms | 3328 KB |
01_21.txt | AC | 8 ms | 3328 KB |
01_22.txt | AC | 8 ms | 3328 KB |
01_23.txt | AC | 8 ms | 3328 KB |
01_24.txt | AC | 8 ms | 3328 KB |
01_25.txt | AC | 8 ms | 3328 KB |
01_26.txt | AC | 8 ms | 3328 KB |
01_27.txt | AC | 8 ms | 3328 KB |
01_28.txt | AC | 8 ms | 3328 KB |
01_29.txt | AC | 8 ms | 3328 KB |
02_00.txt | AC | 17 ms | 3712 KB |
02_01.txt | AC | 16 ms | 3712 KB |
02_02.txt | AC | 17 ms | 3712 KB |
02_03.txt | AC | 17 ms | 3712 KB |
02_04.txt | AC | 16 ms | 3712 KB |
02_05.txt | AC | 16 ms | 3712 KB |
02_06.txt | AC | 17 ms | 3712 KB |
02_07.txt | AC | 16 ms | 3712 KB |
02_08.txt | AC | 17 ms | 3712 KB |
02_09.txt | AC | 17 ms | 3712 KB |
02_10.txt | AC | 16 ms | 3712 KB |
02_11.txt | AC | 16 ms | 3712 KB |
02_12.txt | AC | 16 ms | 3712 KB |
02_13.txt | AC | 17 ms | 3712 KB |
02_14.txt | AC | 17 ms | 3712 KB |
02_15.txt | AC | 17 ms | 3712 KB |
02_16.txt | AC | 16 ms | 3712 KB |
02_17.txt | AC | 16 ms | 3712 KB |
02_18.txt | AC | 17 ms | 3712 KB |
02_19.txt | AC | 17 ms | 3712 KB |
02_20.txt | AC | 17 ms | 3712 KB |
02_21.txt | AC | 17 ms | 3712 KB |
02_22.txt | AC | 16 ms | 3712 KB |
02_23.txt | AC | 16 ms | 3712 KB |
02_24.txt | AC | 16 ms | 3712 KB |
02_25.txt | AC | 17 ms | 3712 KB |
02_26.txt | AC | 17 ms | 3712 KB |
02_27.txt | AC | 17 ms | 3712 KB |
02_28.txt | AC | 16 ms | 3712 KB |
02_29.txt | AC | 16 ms | 3712 KB |
03_00.txt | AC | 511 ms | 14464 KB |
03_01.txt | AC | 459 ms | 14464 KB |
03_02.txt | AC | 427 ms | 14464 KB |
03_03.txt | AC | 430 ms | 14464 KB |
03_04.txt | AC | 435 ms | 14464 KB |
03_05.txt | AC | 280 ms | 14464 KB |
03_06.txt | AC | 320 ms | 14464 KB |
03_07.txt | AC | 359 ms | 14464 KB |
03_08.txt | AC | 380 ms | 14464 KB |
03_09.txt | AC | 399 ms | 14464 KB |
03_10.txt | AC | 393 ms | 14464 KB |
03_11.txt | AC | 320 ms | 14592 KB |
03_12.txt | AC | 367 ms | 14464 KB |
03_13.txt | AC | 375 ms | 14464 KB |
03_14.txt | AC | 395 ms | 14464 KB |
03_15.txt | AC | 419 ms | 14464 KB |
03_16.txt | AC | 414 ms | 14464 KB |
03_17.txt | AC | 362 ms | 14592 KB |
03_18.txt | AC | 352 ms | 14464 KB |
03_19.txt | AC | 388 ms | 14464 KB |
03_20.txt | AC | 405 ms | 14464 KB |
03_21.txt | AC | 440 ms | 14464 KB |
03_22.txt | AC | 433 ms | 14464 KB |
03_23.txt | AC | 397 ms | 14720 KB |
03_24.txt | AC | 383 ms | 14464 KB |
03_25.txt | AC | 419 ms | 14464 KB |
03_26.txt | AC | 425 ms | 14464 KB |
03_27.txt | AC | 442 ms | 14464 KB |
03_28.txt | AC | 443 ms | 14464 KB |
03_29.txt | AC | 404 ms | 14464 KB |
03_30.txt | AC | 425 ms | 14464 KB |
03_31.txt | AC | 437 ms | 14464 KB |
03_32.txt | AC | 453 ms | 14464 KB |
03_33.txt | AC | 455 ms | 14464 KB |
03_34.txt | AC | 469 ms | 14464 KB |