結果
| 問題 |
No.382 シャイな人たち (2)
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-06-26 15:48:00 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 16,886 bytes |
| コンパイル時間 | 3,077 ms |
| コンパイル使用メモリ | 94,280 KB |
| 実行使用メモリ | 67,024 KB |
| 最終ジャッジ日時 | 2024-10-11 23:26:32 |
| 合計ジャッジ時間 | 21,693 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 20 |
ソースコード
package グラフ;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//Pair p=mis(g)
//p.cardinality:最大独立集合の頂点数
//p.choosed_vertices:最大独立集合の頂点
//120頂点で5秒ぐらい。
//verified yukicoder No.382
//
public static void main(String[] args){
new Main().solver();
}
void solver() {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
long S = sc.nextLong();
long Start = System.currentTimeMillis();
Graph g = set_edge(S);
Pair p = ms(g);
int n = g.n;
if (p.cardinality == n) {
System.out.println(-1);
} else {
System.out.println((p.cardinality + 1));
boolean f = false;
for (int i = 0; i < p.choosed_vertices.length; i++) {
if (p.choosed_vertices[i]) {
System.out.print((!f ? "" : " ") + (i + 1));
f = true;
}
}
System.out.println();
}
long T = System.currentTimeMillis();
System.err.println((T - Start) + "ms");
}
sc.close();
}
final long MOD = 1000003;
Graph set_edge(long S) {
S = (S * 12345) % MOD;
int N = (int) (S % 120) + 2;
Graph g = new Graph(N);
S = (S * 12345) % MOD;
long P = S;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
S = (S * 12345) % MOD;
if (S >= P) {
g.set_edge(i, j);
}
}
}
return g;
}
// 無向グラフ
class Graph {
ArrayList<Integer>[] e;
int n;
int[] deg;
boolean[] valid_vertices;// 選ぶことのできる頂点
boolean[] choosed_vertices;// 選ばれた頂点
long v=0;//選ばれた頂点。0は存在しない。1は存在。
Graph(int n) {
this.n = n;
deg = new int[n];
valid_vertices = new boolean[n];
choosed_vertices = new boolean[n];
Arrays.fill(valid_vertices, true);
e = new ArrayList[n];
for (int i = 0; i < n; i++) {
e[i] = new ArrayList<>();
}
}
Graph[] disjoint_set() throws CloneNotSupportedException{
int[] ds=new int[n];
Arrays.fill(ds, -1);
ArrayDeque<Integer> q=new ArrayDeque<>();
int now=0;
for(int i=0;i<n;i++){
if(ds[i]==-1&&valid_vertices[i]){
ds[i]=now;
q.add(i);
while(!q.isEmpty()){
int v=q.poll();
if(!valid_vertices[v])
throw new AssertionError();
ds[v]=now;
for(int j=0;j<e[v].size();j++){
int u=e[v].get(j);
if(ds[u]==-1){
ds[u]=now;
q.add(u);
}else if(ds[u]!=now){
throw new AssertionError();
}
}
}
now++;
}
}
for(int i=0;i<n;i++){
if(ds[i]==-1)
continue;
for(int j=0;j<n;j++){
if(edge(i,j,e)){
if(ds[i]!=ds[j]){
System.out.println(i+" "+j);
System.out.println(ds[i]+" "+ds[j]);
System.out.println(valid_vertices[i]+" "+valid_vertices[j]);
throw new AssertionError();
}
}
}
}
if(now==0){
return new Graph[]{new Graph(0)};
}else if(now==1){
return new Graph[]{copy()};
}
Graph[] gs=new Graph[now];
boolean[][] each_valid_vertices=new boolean[now][n];
for(int i=0;i<n;i++){
int d=ds[i];
if(d==-1)continue;
each_valid_vertices[d][i]=true;
}
for(int i=0;i<now;i++){
gs[i]=induced_subgraph(each_valid_vertices[i]);
}
return gs;
}
// 無向グラフの辺a<->を作成
void set_edge(int a, int b) {
if (!e[a].contains((Integer) b)) {
e[a].add(b);
e[b].add(a);
deg[a]++;
deg[b]++;
}
}
private void delete_undirected_edge(int a, int b) {
e[a].remove((Integer) b);
e[b].remove((Integer) a);
deg[a]--;
deg[b]--;
}
void delete_vertice(int v) {
while (e[v].size() > 0) {
int u = e[v].get(0);
delete_undirected_edge(u, v);
}
valid_vertices[v] = false;
}
void delete_v_with_neighbours(int v) {
while (e[v].size() > 0) {
int u = e[v].get(0);
delete_vertice(u);
}
delete_vertice(v);
}
private Graph induced_subgraph(boolean[] valid_vertices){
Graph g=copy();
int n=g.n;
for(int i=0;i<n;i++){
g.valid_vertices[i]=this.valid_vertices[i];
}
for(int i=0;i<n;i++){
if(!this.valid_vertices[i])
continue;
else if(this.valid_vertices[i]&&(!valid_vertices[i])){
g.delete_vertice(i);
}else if(this.valid_vertices[i]&&valid_vertices[i]){
continue;
}else{
System.out.println(this.valid_vertices[i]);
System.out.println(valid_vertices[i]);
throw new AssertionError();
}
}
return g;
}
Graph copy() {
Graph g = new Graph(this.n);
for (int i = 0; i < n; i++) {
g.deg[i] = deg[i];
}
for (int i = 0; i < n; i++) {
g.valid_vertices[i] = valid_vertices[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < e[i].size(); j++) {
(g.e[i]).add(e[i].get(j));
}
}
return g;
}
}
Pair ms(Graph g){
int n = g.n;
try {
Graph[] gs=g.disjoint_set();
if(gs.length>=2){
Pair p=new Pair(0,new boolean[n]);
for(int i=0;i<gs.length;i++){
p=pair_union(p,ms(gs[i]));
}
return p;
}
} catch (CloneNotSupportedException e1) {
// TODO 自動生成された catch ブロック
e1.printStackTrace();
}
int[] deg = g.deg;
ArrayList<Integer>[] e = g.e;
boolean[] valid_vertices = g.valid_vertices;
int A = -1;// 最も次数の小さい頂点
int B = -1;// Aにつながる頂点のうち最も次数の大きいもの
int deg_me_min = Integer.MAX_VALUE / 4;
int deg_to_max = -Integer.MAX_VALUE / 4;
for (int i = 0; i < n; i++) {
if (!valid_vertices[i])
continue;
if (deg[i] < deg_me_min) {
A = i;
deg_me_min = deg[A];
if (deg_me_min <= 1) {
g.delete_v_with_neighbours(A);
Pair p = ms(g);
p.choosed_vertices[A] = true;
p.cardinality++;
return p;
}
B = e[A].get(0);
deg_to_max = deg[B];
for (int j = 1; j < e[A].size(); j++) {
int u = e[A].get(j);
if (deg[u] > deg_to_max) {
B = u;
deg_to_max = deg[B];
}
}
} else if (deg[i] == deg_me_min) {
for (int j = 0; j < e[A].size(); j++) {
int u = e[A].get(j);
if (deg[u] > deg_to_max) {
A = i;
B = u;
deg_to_max = deg[B];
}
}
}
}
if (A == -1 && B == -1)
return new Pair(0, new boolean[n]);
if (A == -1 || B == -1)
throw new AssertionError("A==-1||B==-1");
if (deg[A] > deg[B])
throw new AssertionError("deg[A]>deg[B]");
if (deg[A] == 2) {
int B2 = -1;
if (e[A].get(0) != B) {
B2 = e[A].get(0);
} else if (e[A].get(1) != B) {
B2 = e[A].get(1);
}
if (edge(B2,B,e)) {
g.delete_v_with_neighbours(A);
Pair p = ms(g);
p.cardinality++;
p.choosed_vertices[A] = true;
return p;
}else{
Graph g2 = g.copy();
g2.delete_v_with_neighbours(B);
g2.delete_v_with_neighbours(B2);
Pair p = ms(g2);
p.cardinality += 2;
p.choosed_vertices[B] = true;
p.choosed_vertices[B2] = true;
ArrayList<Integer> neighbour = new ArrayList<>();
for (int i = 0; i < 2; i++) {
int u = (i == 0 ? B : B2);// u is an element of N(A)
for (int j = 0; j < e[u].size(); j++) {
int v = e[u].get(j);
if (v == A)
continue;
if (neighbour.contains(v))
continue;
neighbour.add(v);
}
}
g.delete_v_with_neighbours(A);
Pair p2 = ms2(g, neighbour);
p2.cardinality++;
p2.choosed_vertices[A] = true;
p = pair_bigger(p, p2);
return p;
}
}
if (deg[A] == 3) {
Graph g2 = g.copy();
g2.delete_v_with_neighbours(A);
Pair p2 = ms(g2);
p2.cardinality++;
p2.choosed_vertices[A] = true;
ArrayList<Integer> S=new ArrayList<>();
for (int i = 0; i < e[A].size(); i++) {
S.add(e[A].get(i));
}
g.delete_vertice(A);
Pair p1 = ms2(g, S);
return pair_bigger(p1, p2);
}
ArrayList<Integer> a=new ArrayList<>();
ArrayList<Integer> b=new ArrayList<>();
a.add(A);
b.add(B);
ArrayList<Integer> NA=union(e[A],a);
ArrayList<Integer> NB=union(e[B],b);
if (is_subset(NA, NB)) {
g.delete_vertice(B);
Pair p = ms(g);
return p;
}
Graph g2 = g.copy();
g2.delete_v_with_neighbours(B);
g.delete_vertice(B);
Pair p1 = ms(g);
Pair p2 = ms(g2);
p2.cardinality++;
p2.choosed_vertices[B] = true;
return pair_bigger(p1, p2);
}
// Sから少なくとも二つ使う場合を考える。
Pair ms2(Graph g, ArrayList<Integer> S) {
int[] deg = g.deg;
ArrayList<Integer>[] e = g.e;
boolean[] valid_vertices = g.valid_vertices;
int n = g.n;
Pair p = new Pair(0, new boolean[n]);
if (S.size() <= 1)
return p;
else if (S.size() == 2) {
int u = S.get(0);
int v = S.get(1);
if (edge(u,v,e))
return p;
else {
g.delete_v_with_neighbours(u);
g.delete_v_with_neighbours(v);
p = ms(g);
p.cardinality += 2;
p.choosed_vertices[u] = true;
p.choosed_vertices[v] = true;
return p;
}
} else if (S.size() == 3) {
int[] s = new int[3];
for (int i = 0; i < 3; i++) {
s[i] = S.get(i);
}
// arrange s[i] so that s[0] is the smallest one;
if (deg[s[0]] > deg[s[1]]) {
int d = s[0];
s[0] = s[1];
s[1] = d;
}
if (deg[s[0]] > deg[s[2]]) {
int d = s[0];
s[0] = s[2];
s[2] = d;
}
if (deg[s[0]] == 0) {
g.delete_vertice(s[0]);
S.remove((Integer) s[0]);
p = ms1(g, S);
p.cardinality++;
p.choosed_vertices[s[0]] = true;
return p;
} else if (edge(s[0], s[1], e) && edge(s[1], s[2], e) && edge(s[2], s[0], e)) {
return p;
}
for (int i = 0; i < 3; i++) {
int u = s[(i + 1) % 3];
int v = s[(i + 2) % 3];
if (edge(u, s[i], e) && edge(s[i], v, e)) {
g.delete_v_with_neighbours(u);
g.delete_v_with_neighbours(v);
p = ms(g);
p.cardinality += 2;
p.choosed_vertices[u] = true;
p.choosed_vertices[v] = true;
return p;
}
}
for (int i = 0; i < 3; i++) {
int u = s[(i + 1) % 3];
int v = s[(i + 2) % 3];
if (edge(u, v, e)) {
g.delete_v_with_neighbours(s[i]);
S.remove((Integer) s[i]);
p = ms1(g, S);
p.cardinality++;
p.choosed_vertices[s[i]] = true;
return p;
}
}
for (int i = 0; i < 3; i++) {
int u = s[i];
int v = s[(i + 1) % 3];
ArrayList<Integer> intersection = intersection(e[u], e[v]);
if (intersection.size() >= 1) {
int w = intersection.get(0);
g.delete_vertice(w);
p = ms2(g, S);
return p;
}
}
if (deg[s[0]] == 1) {
g.delete_v_with_neighbours(s[0]);
S.remove((Integer) s[0]);
p = ms1(g, S);
p.cardinality++;
p.choosed_vertices[s[0]] = true;
return p;
} else {
Graph g2 = g.copy();
g2.delete_v_with_neighbours(s[0]);
S.remove((Integer) s[0]);
p = ms1(g2, S);
p.cardinality++;
p.choosed_vertices[s[0]] = true;
g.delete_v_with_neighbours(s[2]);
g.delete_v_with_neighbours(s[1]);
ArrayList<Integer> S2 = new ArrayList<>();
for (int i = 0; i < e[s[0]].size(); i++) {
S2.add(e[s[0]].get(i));
}
g.delete_vertice(s[0]);
Pair p2=ms(g);
// Pair p2 = ms2(g,S2);
p2.cardinality+=2;
p2.choosed_vertices[s[2]]=true;
p2.choosed_vertices[s[1]]=true;
return pair_bigger(p, p2);
}
}
if (S.size() == 4) {
int min_v = S.get(0);
for (int i = 0; i < 4; i++) {
int v = S.get(i);
if (deg[v] < deg[min_v]) {
min_v = v;
}
}
if (deg[min_v] <= 3) {
return ms(g);
} else {
Graph g2 = g.copy();
g.delete_v_with_neighbours(min_v);
p = ms(g);
p.cardinality++;
p.choosed_vertices[min_v] = true;
g2.delete_vertice(min_v);
S.remove((Integer) min_v);
Pair p2 = ms2(g2, S);
return pair_bigger(p, p2);
}
}
if (S.size() <= 4)
throw new AssertionError();
return ms(g);
}
Pair ms1(Graph g, ArrayList<Integer> S) {
int[] deg = g.deg;
ArrayList<Integer>[] e = g.e;
boolean[] valid_vertices = g.valid_vertices;
int n = g.n;
for(int i=0;i<S.size();i++){
int v=S.get(i);
if(!valid_vertices[v]){
throw new AssertionError();
}
}
if (S.size() != 2) {
throw new AssertionError("S.size()!=2");
}
int s1 = S.get(0);
int s2 = S.get(1);
if (deg[s1] > deg[s2]) {
int d = s1;
s1 = s2;
s2 = d;
}
if (deg[s1] <= 1) {
return ms(g);
} else if (edge(s1,s2,e)) {
if (deg[s1] <= 3)
return ms(g);
else {
Graph g2 = g.copy();
g.delete_v_with_neighbours(s1);
Pair p1 = ms(g);
p1.cardinality++;
p1.choosed_vertices[s1] = true;
g2.delete_v_with_neighbours(s2);
Pair p2 = ms(g2);
p2.cardinality++;
p2.choosed_vertices[s2] = true;
return pair_bigger(p1, p2);
}
}
ArrayList<Integer> intersection = intersection(e[s1], e[s2]);
if (intersection.size() != 0) {
for (int i = 0; i < intersection.size(); i++) {
g.delete_vertice(intersection.get(i));
}
return ms1(g, S);
} else if (deg[s2] == 2) {
if (deg[s1] != 2) {
throw new AssertionError("deg[s1]!=2");
}
int E = e[s1].get(0);
int F = e[s1].get(1);
if (edge(E,F,e)) {
g.delete_v_with_neighbours(s1);
Pair p = ms(g);
p.cardinality++;
p.choosed_vertices[s1] = true;
return p;
}
ArrayList<Integer> union = union(e[E], e[F]);
union.remove((Integer) s1);
if (is_subset(union, e[s2])) {
g.delete_v_with_neighbours(E);
g.delete_v_with_neighbours(F);
g.delete_v_with_neighbours(s2);
Pair p = ms(g);
p.cardinality += 3;
p.choosed_vertices[E] = true;
p.choosed_vertices[F] = true;
p.choosed_vertices[s2] = true;
return p;
} else {
Graph g2 = g.copy();
g.delete_v_with_neighbours(E);
g.delete_v_with_neighbours(F);
g.delete_v_with_neighbours(s2);
Pair p = ms(g);
p.cardinality += 3;
p.choosed_vertices[E] = true;
p.choosed_vertices[F] = true;
p.choosed_vertices[s2] = true;
g2.delete_v_with_neighbours(s1);
Pair p2 = ms(g2);
p2.cardinality++;
p2.choosed_vertices[s1] = true;
return pair_bigger(p, p2);
}
} else {
Graph g2 = g.copy();
g.delete_v_with_neighbours(s2);
Pair p = ms(g);
p.cardinality++;
p.choosed_vertices[s2]=true;
g2.delete_v_with_neighbours(s1);
ArrayList<Integer> S2=new ArrayList<>();
for(int i=0;i<e[s2].size();i++){
S2.add(e[s2].get(i));
}
g2.delete_vertice(s2);
Pair p2 = ms2(g2, S2);
p2.cardinality++;
p2.choosed_vertices[s1] = true;
p = pair_bigger(p, p2);
return p;
}
}
class Pair {
int cardinality;
boolean[] choosed_vertices;
Pair(int cardinality, boolean[] choosed_vertices) {
this.cardinality = cardinality;
this.choosed_vertices = choosed_vertices;
}
}
boolean is_subset(ArrayList<Integer> subset, ArrayList<Integer> superset) {
if (subset.size() > superset.size())
return false;
for (int i = 0; i < subset.size(); i++) {
if (!superset.contains(subset)) {
return false;
}
}
return true;
}
ArrayList<Integer> union(ArrayList<Integer> s1, ArrayList<Integer> s2) {
ArrayList<Integer> ret = new ArrayList<>();
for (int i = 0; i < s1.size(); i++) {
if (!ret.contains(s1.get(i))) {
ret.add(s1.get(i));
}
}
for (int i = 0; i < s2.size(); i++) {
if (!ret.contains(s2.get(i))) {
ret.add(s2.get(i));
}
}
return ret;
}
// 頂点u,v間に辺が存在するときtrueを返す。
boolean edge(int u, int v, ArrayList<Integer>[] e) {
if (e[u].contains(v))
return true;
else
return false;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
ArrayList intersection(ArrayList s1, ArrayList s2) {
ArrayList ret = new ArrayList<>();
for (int i = 0; i < s1.size(); i++) {
if (s2.contains(s1.get(i))) {
ret.add(s1.get(i));
}
}
return ret;
}
Pair pair_bigger(Pair p1, Pair p2) {
return p1.cardinality > p2.cardinality ? p1 : p2;
}
Pair pair_union(Pair p1,Pair p2){
int n=p1.choosed_vertices.length;
int cardinality=0;
boolean[] d=new boolean[n];
for(int i=0;i<n;i++){
if(p1.choosed_vertices[i]&&p2.choosed_vertices[i]){
throw new AssertionError();
}
if(p1.choosed_vertices[i]||p2.choosed_vertices[i]){
d[i]=true;
cardinality++;
}
}
return new Pair(cardinality,d);
}
class DJSet{
int n;//the number of vertices
int[] d;
DJSet(int n){
this.n=n;
d=new int[n];
Arrays.fill(d, -1);
}
int root(int x){
return d[x]<0?x:root(d[x]);
}
boolean setUnion(int x,int y){
x=root(x);
y=root(y);
if(x!=y){
if(x<y){
int d=x;
x=y;
y=d;
}
//x>y
d[y]+=d[x];
d[x]=y;
}
return x!=y;
}
boolean equiv(int x,int y){
return root(x)==root(y);
}
//xを含む木のNodeの数
int size(int x){
return d[root(x)]*(-1);
}
//連結グラフの数
int count(){
int ct=0;
for(int u:d){
if(u<0)ct++;
}
return ct;
}
}
void tr(Object...o){System.out.println(Arrays.deepToString(o));}
}