library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj/2513.test.cpp
- View this file on GitHub
- Last update: 2020-10-27 16:27:26+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2513
Depends on
Code
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2513
#include<bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../matching/bipartite.cpp"
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n;
while(cin>>n,n){
vector<vector<int>> xss;
vector<vector<int>> yss;
for(int i=0;i<n;i++){
vector<int> xs(3),ys(3);
for(int j=0;j<3;j++) cin>>xs[j]>>ys[j];
xss.emplace_back(xs);
yss.emplace_back(ys);
}
const int T = 16;
int dx[T][4]={{ 0,-1, 1, 0},
{ 0, 1, 1, 2},
{ 0, 0, 1,-1},
{ 0,-1,-1,-2},
{ 0, 1, 2, 3},
{ 0,-2,-1, 1},
{-1, 0, 1, 2},
{-3,-2,-1, 0},
{ 0, 0,-1,-1},
{ 1, 1, 0, 0},
{ 0, 0, 1, 1},
{-1,-1, 0, 0},
{-1, 0, 0, 1},
{-2,-1,-1, 0},
{ 1, 0, 0,-1},
{ 2, 1, 1, 0},
};
int dy[T][4]={{ 0, 0, 0,-1},
{ 0, 1, 0, 0},
{ 0,-1,-1,-1},
{ 0, 0, 1, 0},
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 0,-1,-1,-2},
{ 1, 0, 0,-1},
{ 0,-1,-1,-2},
{ 1, 0, 0,-1},
{ 0, 0,-1,-1},
{ 1, 1, 0, 0},
{ 0, 0,-1,-1},
{ 1, 1, 0, 0},
};
using P = pair<int, int>;
int m=n;
map<P, int> mp;
vector<set<int>> G(n);
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
for(int j=0;j<3;j++)
mp[P(xs[j],ys[j])]=m++;
}
vector<set<int> > H(n);
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
set<P> tmp;
for(int j=0;j<3;j++)
tmp.emplace(xs[j],ys[j]);
int sy=((xs[0]+ys[0])%2==0?1:-1);
for(int j=0;j<T;j++){
set<P> res;
for(int k=0;k<4;k++)
res.emplace(xs[0]+dx[j][k],ys[0]+sy*dy[j][k]);
int cnt=0;
P uku;
for(auto p:res){
if(tmp.count(p)){
cnt++;
continue;
}
uku=p;
}
if(cnt!=3) continue;
if(!mp.count(uku)) mp[uku]=m++;
G[i].emplace(mp[uku]);
}
}
Bipartite bm(m);
for(int i=0;i<n;i++)
for(int j:G[i])
bm.add_edge(i,j);
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
for(int j=0;j<3;j++)
bm.disable(mp[P(xs[j],ys[j])]);
}
int res=bm.build();
if(res==n){
cout<<"Valid"<<"\n";
continue;
}
if(res+4<n){
cout<<"Invalid"<<"\n";
continue;
}
set<int> ans;
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
res+=bm.disable(i);
for(int j=0;j<3;j++)
res+=bm.enable(mp[P(xs[j],ys[j])]);
if(res+1==n) ans.emplace(i);
for(int j=0;j<3;j++)
res+=bm.disable(mp[P(xs[j],ys[j])]);
res+=bm.enable(i);
}
if(ans.empty()){
cout<<"Invalid"<<"\n";
}else{
cout<<"Remove"<<"\n";
for(int i:ans) cout<<i+1<<"\n";
}
}
cout<<flush;
return 0;
}#line 1 "test/aoj/2513.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2513
#include<bits/stdc++.h>
using namespace std;
#define call_from_test
#line 1 "matching/bipartite.cpp"
#line 3 "matching/bipartite.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(N M)
struct Bipartite{
int time;
vector< vector<int> > G;
vector<int> match,used,dead;
Bipartite(int n):
time(0),G(n),match(n,-1),used(n,-1),dead(n,0){}
void add_edge(int u,int v){
G[u].emplace_back(v);
G[v].emplace_back(u);
}
int dfs(int v){
used[v]=time;
for(int u:G[v]){
if(dead[u]) continue;
int w=match[u];
if((w<0) or (used[w]<time and dfs(w))){
match[v]=u;
match[u]=v;
return 1;
}
}
return 0;
}
int build(){
int res=0;
for(int v=0;v<(int)G.size();v++){
if(dead[v] or ~match[v]) continue;
time++;
res+=dfs(v);
}
return res;
}
int disable(int v){
assert(!dead[v]);
int u=match[v];
if(~u) match[u]=-1;
match[v]=-1;
dead[v]=1;
time++;
return ~u?dfs(u)-1:0;
}
int enable(int v){
assert(dead[v]);
dead[v]=0;
time++;
return dfs(v);
}
int cut_edge(int u,int v){
assert(find(G[u].begin(),G[u].end(),v)!=G[u].end());
assert(find(G[v].begin(),G[v].end(),u)!=G[v].end());
G[u].erase(find(G[u].begin(),G[u].end(),v));
G[v].erase(find(G[v].begin(),G[v].end(),u));
if(match[u]==v){
match[u]=match[v]=-1;
return 1;
}
return 0;
}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
return 0;
}
#endif
#line 8 "test/aoj/2513.test.cpp"
#undef call_from_test
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n;
while(cin>>n,n){
vector<vector<int>> xss;
vector<vector<int>> yss;
for(int i=0;i<n;i++){
vector<int> xs(3),ys(3);
for(int j=0;j<3;j++) cin>>xs[j]>>ys[j];
xss.emplace_back(xs);
yss.emplace_back(ys);
}
const int T = 16;
int dx[T][4]={{ 0,-1, 1, 0},
{ 0, 1, 1, 2},
{ 0, 0, 1,-1},
{ 0,-1,-1,-2},
{ 0, 1, 2, 3},
{ 0,-2,-1, 1},
{-1, 0, 1, 2},
{-3,-2,-1, 0},
{ 0, 0,-1,-1},
{ 1, 1, 0, 0},
{ 0, 0, 1, 1},
{-1,-1, 0, 0},
{-1, 0, 0, 1},
{-2,-1,-1, 0},
{ 1, 0, 0,-1},
{ 2, 1, 1, 0},
};
int dy[T][4]={{ 0, 0, 0,-1},
{ 0, 1, 0, 0},
{ 0,-1,-1,-1},
{ 0, 0, 1, 0},
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 0, 0, 0, 0},
{ 0,-1,-1,-2},
{ 1, 0, 0,-1},
{ 0,-1,-1,-2},
{ 1, 0, 0,-1},
{ 0, 0,-1,-1},
{ 1, 1, 0, 0},
{ 0, 0,-1,-1},
{ 1, 1, 0, 0},
};
using P = pair<int, int>;
int m=n;
map<P, int> mp;
vector<set<int>> G(n);
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
for(int j=0;j<3;j++)
mp[P(xs[j],ys[j])]=m++;
}
vector<set<int> > H(n);
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
set<P> tmp;
for(int j=0;j<3;j++)
tmp.emplace(xs[j],ys[j]);
int sy=((xs[0]+ys[0])%2==0?1:-1);
for(int j=0;j<T;j++){
set<P> res;
for(int k=0;k<4;k++)
res.emplace(xs[0]+dx[j][k],ys[0]+sy*dy[j][k]);
int cnt=0;
P uku;
for(auto p:res){
if(tmp.count(p)){
cnt++;
continue;
}
uku=p;
}
if(cnt!=3) continue;
if(!mp.count(uku)) mp[uku]=m++;
G[i].emplace(mp[uku]);
}
}
Bipartite bm(m);
for(int i=0;i<n;i++)
for(int j:G[i])
bm.add_edge(i,j);
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
for(int j=0;j<3;j++)
bm.disable(mp[P(xs[j],ys[j])]);
}
int res=bm.build();
if(res==n){
cout<<"Valid"<<"\n";
continue;
}
if(res+4<n){
cout<<"Invalid"<<"\n";
continue;
}
set<int> ans;
for(int i=0;i<n;i++){
auto &xs=xss[i];
auto &ys=yss[i];
res+=bm.disable(i);
for(int j=0;j<3;j++)
res+=bm.enable(mp[P(xs[j],ys[j])]);
if(res+1==n) ans.emplace(i);
for(int j=0;j<3;j++)
res+=bm.disable(mp[P(xs[j],ys[j])]);
res+=bm.enable(i);
}
if(ans.empty()){
cout<<"Invalid"<<"\n";
}else{
cout<<"Remove"<<"\n";
for(int i:ans) cout<<i+1<<"\n";
}
}
cout<<flush;
return 0;
}