Submission #527776
Source Code Expand
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct BIT{
int n;
vector<int>dat;
void init(int _n){
n=_n;
dat.clear();
dat.resize(n+1,0);
}
void add(int k,int x){
for(k++;k<=n;k+=k&-k)dat[k]+=x;
}
int sum(int k){
int ret=0;
for(k++;k;k-=k&-k)ret+=dat[k];
return ret;
}
};
struct UF{
int n;
vector<int>par;
void init(int _n){
n=_n;
par.clear();
par.resize(n);
for(int i=0;i<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];
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();
}
BIT bit;
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++){
int v=bit.sum(vec[i]-1);
val+=i-v;
//cout<<"**"<<i-v<<endl;
bit.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 uf;uf.init(N);
for(int i=0;i<M;i++){
int a=E[i][0],b=E[i][1];
if(uf.same(a,b))return -1;
uf.unite(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);
for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";cout<<endl;
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 |
1056 ms |
265576 KB |
subtask1/2 |
TLE |
1055 ms |
265580 KB |
subtask1/3 |
TLE |
1056 ms |
265580 KB |
subtask1/4 |
TLE |
1052 ms |
265588 KB |
subtask1/5 |
TLE |
1058 ms |
265652 KB |
subtask1/6 |
TLE |
1054 ms |
265712 KB |
subtask1/7 |
AC |
31 ms |
3352 KB |
subtask2/1 |
TLE |
1057 ms |
265960 KB |
subtask2/2 |
TLE |
1054 ms |
266604 KB |
subtask2/3 |
TLE |
1056 ms |
269164 KB |
subtask2/4 |
TLE |
1098 ms |
270388 KB |
subtask2/5 |
TLE |
1079 ms |
270448 KB |
subtask2/6 |
TLE |
1070 ms |
270444 KB |
subtask3/1 |
AC |
58 ms |
5012 KB |
subtask3/2 |
AC |
63 ms |
5468 KB |
subtask3/3 |
TLE |
1058 ms |
267692 KB |
subtask3/4 |
WA |
70 ms |
6292 KB |
subtask3/5 |
AC |
109 ms |
8016 KB |
subtask3/6 |
WA |
143 ms |
10132 KB |
subtask3/7 |
WA |
188 ms |
11924 KB |
subtask3/8 |
WA |
180 ms |
11924 KB |
subtask3/9 |
AC |
37 ms |
4064 KB |