Submission #131378
Source Code Expand
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <queue> #include <cstring> #define SIZE 100005 using namespace std; typedef long long int ll; typedef pair <int,int> P; struct BIT { int bit[SIZE]; int n; void init(int _n) { memset(bit,0,sizeof(bit)); n=_n; } void add(int k,int x) { while(k<=n) { bit[k]+=x; k+=k&-k; } } int sum(int k) { int ret=0; while(k>0) { ret+=bit[k]; k-=k&-k; } return ret; } }; BIT bit; vector <int> vec[SIZE]; bool use[SIZE]; int last; ll solve(int v,int cnt) { bit.init(cnt+2); int bef=-1,now=v; ll ret=0; bool up=true; while(up) { use[now]=true; ret+=(ll) bit.sum(now+1); bit.add(now+1,1); up=false; for(int i=0;i<vec[now].size();i++) { if(vec[now][i]!=bef) { int to=vec[now][i]; bef=now; now=to; up=true; break; } } } last=now; return ret; } long long best_swap(int n, int m,int E[][2]) { vector <P> in; for(int i=0;i<m;i++) { int l=E[i][0],r=E[i][1]; if(l>r) swap(l,r); in.push_back(P(l,r)); } sort(in.begin(),in.end()); for(int i=0;i<m;i++) { if(i>0&&in[i]==in[i-1]) continue; int l=in[i].first,r=in[i].second; vec[l].push_back(r); vec[r].push_back(l); } for(int i=0;i<n;i++) if(vec[i].size()>2) return -1; ll ret=0; for(int i=0;i<n;i++) { if(!use[i]&&vec[i].size()==1) { ll pl=solve(i,n); pl=min(pl,solve(last,n)); ret+=pl; } } for(int i=0;i<n;i++) if(!use[i]&&vec[i].size()==2) return -1; return ret; }
Submission Info
Submission Time | |
---|---|
Task | A - 国際道迷いオリンピック(International Michimayoi Olympic) |
User | yutaka1999 |
Language | IOI-Style C++ (GCC 5.4.1) |
Score | 54 |
Code Size | 1620 Byte |
Status | TLE |
Exec Time | 1031 ms |
Memory | 9756 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 10 / 10 | 44 / 44 | 0 / 46 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7 |
Subtask2 | subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6 |
Subtask3 | subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask3/1, subtask3/2, subtask3/3, subtask3/4, subtask3/5, subtask3/6, subtask3/7, subtask3/8, subtask3/9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask1/1 | AC | 27 ms | 3484 KB |
subtask1/2 | AC | 25 ms | 3612 KB |
subtask1/3 | AC | 26 ms | 3492 KB |
subtask1/4 | AC | 26 ms | 3444 KB |
subtask1/5 | AC | 26 ms | 3560 KB |
subtask1/6 | AC | 26 ms | 3496 KB |
subtask1/7 | AC | 25 ms | 3116 KB |
subtask2/1 | AC | 29 ms | 3748 KB |
subtask2/2 | AC | 43 ms | 4388 KB |
subtask2/3 | AC | 87 ms | 7068 KB |
subtask2/4 | AC | 110 ms | 8220 KB |
subtask2/5 | AC | 150 ms | 8220 KB |
subtask2/6 | AC | 108 ms | 8296 KB |
subtask3/1 | AC | 52 ms | 4516 KB |
subtask3/2 | AC | 53 ms | 5016 KB |
subtask3/3 | AC | 964 ms | 5412 KB |
subtask3/4 | TLE | 1031 ms | 6172 KB |
subtask3/5 | AC | 110 ms | 7708 KB |
subtask3/6 | TLE | 1031 ms | 8980 KB |
subtask3/7 | AC | 954 ms | 9756 KB |
subtask3/8 | AC | 190 ms | 9756 KB |
subtask3/9 | AC | 26 ms | 3056 KB |