Submission #527793
Source Code Expand
#include<bits/stdc++.h>
#define int long long
using namespace std;
int bit_n,bit[1010101];
void bit_init(int n){bit_n=n;for(int i=0;i<=bit_n;i++)bit[i]=0;}
void add(int k,int x){for(k++;k<=bit_n;k++)bit[k]+=x;}
int sum(int k){int ret=0;for(k++;k;k-=k&-k)ret+=bit[k];return ret;}
int uf_n,par[1010101];
void uf_init(int n){uf_n=n;for(int i=0;i<uf_n;i++)par[i]=i;}
int find(int x){return x==par[x]?x:par[x]=find(par[x]);}
void unite(int x,int y){x=find(x);y=find(y);if(x!=y)par[y]=x;}
bool same(int x,int y){return find(x)==find(y);}
vector<int>G[100000];
bool used[100000];
set<pair<int,int> >S;
int solve(vector<int>vec){
vector<int>xs;
for(int i=0;i<vec.size();i++)xs.push_back(vec[i]);
sort(xs.begin(),xs.end());
for(int i=0;i<vec.size();i++){
vec[i]=lower_bound(xs.begin(),xs.end(),vec[i])-xs.begin();
}
int ret=LLONG_MAX/100;
for(int Latte=0;Latte<2;Latte++){
bit_init(xs.size());
int val=0;
for(int i=0;i<vec.size();i++){
val+=i-sum(vec[i]-1);
add(vec[i],1);
}
ret=min(ret,val);
for(int i=0;i<vec.size();i++){
vec[i]=xs.size()-1-vec[i];
}
}
return ret;
}
int best_swap(signed N, signed M,signed E[][2]){
for(int i=0;i<M;i++){
int a=E[i][0],b=E[i][1];
G[a].push_back(b);
G[b].push_back(a);
}
for(int i=0;i<N;i++){
sort(G[i].begin(),G[i].end());
G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
}
uf_init(N);
for(int i=0;i<M;i++){
int a=E[i][0],b=E[i][1];
if(S.find(pair<int,int>(min(a,b),max(a,b)))!=S.end())continue;
if(same(a,b))return -1;
unite(a,b);
S.insert(pair<int,int>(min(a,b),max(a,b)));
}
for(int i=0;i<N;i++){
if(G[i].size()>2)return -1;
}
int ans=0;
for(int i=0;i<N;i++){
if(used[i]||G[i].size()!=1)continue;
used[i]=true;
vector<int>vec;
vec.push_back(i);
int v=G[i][0];
int prev=i;
while(G[v].size()!=1){
int a=G[v][0],b=G[v][1];
if(a==prev){
vec.push_back(b);
v=b;
}
else{
vec.push_back(a);
v=a;
}
used[v]=true;
}
vec.push_back(v);
ans+=solve(vec);
}
return ans;
}
/*
int N,M,E[100000][2];
signed main(){
cin>>N>>M;
for(int i=0;i<M;i++){
int a,b;
cin>>a>>b;
E[i][0]=a;E[i][1]=b;
}
cout<<best_swap(N,M,E)<<endl;
return 0;
}
*/
Submission Info
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 10 |
0 / 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 |
TLE |
1053 ms |
265520 KB |
subtask1/2 |
TLE |
1064 ms |
265620 KB |
subtask1/3 |
TLE |
1052 ms |
265616 KB |
subtask1/4 |
TLE |
1051 ms |
265620 KB |
subtask1/5 |
TLE |
1072 ms |
265740 KB |
subtask1/6 |
TLE |
1078 ms |
265616 KB |
subtask1/7 |
AC |
31 ms |
3256 KB |
subtask2/1 |
TLE |
1054 ms |
266124 KB |
subtask2/2 |
TLE |
1053 ms |
267796 KB |
subtask2/3 |
TLE |
1095 ms |
271636 KB |
subtask2/4 |
TLE |
1066 ms |
249992 KB |
subtask2/5 |
TLE |
1072 ms |
242056 KB |
subtask2/6 |
TLE |
1065 ms |
228236 KB |
subtask3/1 |
AC |
61 ms |
5028 KB |
subtask3/2 |
AC |
96 ms |
7860 KB |
subtask3/3 |
TLE |
1065 ms |
269708 KB |
subtask3/4 |
TLE |
1072 ms |
269576 KB |
subtask3/5 |
AC |
192 ms |
14264 KB |
subtask3/6 |
TLE |
1063 ms |
226704 KB |
subtask3/7 |
TLE |
1062 ms |
198928 KB |
subtask3/8 |
TLE |
1056 ms |
172044 KB |
subtask3/9 |
AC |
33 ms |
4020 KB |