Submission #527834
Source Code Expand
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct BIT{
int N;
vector<int>bit;
void init(int n){
N=n;
bit.resize(N,0);
}
void inc(int k){
for(k++;k<=N;k+=k&-k)bit[k]++;
}
void dec(int k){
for(k++;k<=N;k+=k&-k)bit[k]--;
}
int sum(int k){
int ret=0;
for(k++;k;k-=k&-k)ret+=bit[k];
return ret;
}
};
struct UF{
int N;
vector<int>par,sz;
void init(int n){
N=n;
par.resize(N);
sz.resize(N,1);
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)return;
if(sz[x]<sz[y])swap(x,y);
par[y]=x;
sz[x]+=sz[y];
}
bool same(int x,int y){
return find(x)==find(y);
}
};
vector<int>G[100000];
bool used[100000];
BIT bit;
set<pair<int,int> >S;
int solve(vector<int>&vec){
int ret=0;
for(int i=0;i<vec.size();i++){
ret+=i-bit.sum(vec[i]-1);
bit.inc(vec[i]);
}
for(int i=0;i<vec.size();i++){
bit.dec(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(S.find(pair<int,int>(min(a,b),max(a,b)))!=S.end())continue;
if(uf.same(a,b))return -1;
uf.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;
bit.init(N);
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 |
WA |
35 ms |
3352 KB |
subtask1/2 |
WA |
31 ms |
3352 KB |
subtask1/3 |
WA |
33 ms |
3352 KB |
subtask1/4 |
WA |
33 ms |
3348 KB |
subtask1/5 |
WA |
34 ms |
3476 KB |
subtask1/6 |
WA |
35 ms |
3472 KB |
subtask1/7 |
AC |
34 ms |
3432 KB |
subtask2/1 |
WA |
41 ms |
3980 KB |
subtask2/2 |
WA |
63 ms |
5844 KB |
subtask2/3 |
WA |
154 ms |
12632 KB |
subtask2/4 |
WA |
202 ms |
15828 KB |
subtask2/5 |
WA |
204 ms |
15840 KB |
subtask2/6 |
WA |
203 ms |
15828 KB |
subtask3/1 |
AC |
61 ms |
5328 KB |
subtask3/2 |
AC |
99 ms |
8272 KB |
subtask3/3 |
WA |
81 ms |
8280 KB |
subtask3/4 |
WA |
107 ms |
9952 KB |
subtask3/5 |
AC |
208 ms |
14992 KB |
subtask3/6 |
WA |
255 ms |
16524 KB |
subtask3/7 |
WA |
316 ms |
18572 KB |
subtask3/8 |
WA |
328 ms |
19488 KB |
subtask3/9 |
AC |
39 ms |
5716 KB |