oj.uz

Submission #651974

# Submission time Handle Problem Language Result Execution time Memory
651974 2022-10-20T22:14:09 Z ziduo Potemkin cycle (CEOI15_indcyc) Java 11
70 / 100
 1000 ms 21380 KB 
import java.io.*;
import java.util.*;
public class indcyc {

	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    int n = Integer.parseInt(st.nextToken());
	    int r = Integer.parseInt(st.nextToken());
	    ArrayList<Integer>[] edges = new ArrayList[n];
	    for(int i=0; i<n; i++)edges[i] = new ArrayList<>();
	    for(int i=0; i<r; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	int a = Integer.parseInt(st.nextToken())-1;
	    	int b = Integer.parseInt(st.nextToken())-1;
	    	edges[a].add(b);
	    	edges[b].add(a);
	    	
	    }
	    boolean[][] same = new boolean[n][n];
	    for(int i=0; i<n; i++)for(int j=0; j<edges[i].size(); j++)same[i][edges[i].get(j)]=true;
	    LinkedList<Integer> list = new LinkedList<>();
	    for(int i=0; i<n; i++)for(int j: edges[i]) {
	    	int[] dist = new int[n];
	    	Arrays.fill(dist, -1);
	    	dist[j]=i;
	    	for(int tar: edges[j])if(!same[tar][i]&&tar!=i) {
	    		list.add(tar);
	    		dist[tar]=j;
	    	}
	    	while(!list.isEmpty()) {
	    		int s= list.size();
	    		for(int k=0; k<s; k++) {
	    			int num = list.removeFirst();
	    			for(int tar: edges[num]) {
	    				if(dist[tar]!=-1||(same[j][tar]&&tar!=i))continue;
	    				dist[tar] = num;
	    				if(tar==i)break;
	    				list.add(tar);
	    			}
	    			if(dist[i]!=-1)break;
	    		}
	    		if(dist[i]!=-1)break;
	    	}
	    	list.clear();
	    	if(dist[i]!=-1) {
	    		int cur = dist[i];
	    		while(cur!=i) {
	    			out.write((cur+1)+" ");
	    			cur = dist[cur];
	    		}
	    		out.write((i+1)+"");
	    		out.flush();
	    		out.close();
	    		return;
	    	}
	    }
	    out.write("no");
	    out.flush();
	    out.close();

	}

}

Compilation message

Note: indcyc.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 11016 KB Output is correct
2 Correct 65 ms 8476 KB Output is correct
3 Correct 64 ms 8292 KB Output is correct
4 Correct 64 ms 8228 KB Output is correct
5 Correct 62 ms 8292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 10456 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10216 KB Output is correct
2 Correct 65 ms 8484 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 10416 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 14216 KB Output is correct
2 Correct 159 ms 15056 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 15488 KB Output is correct
2 Correct 276 ms 16376 KB Output is correct
3 Correct 348 ms 16284 KB Output is correct
4 Correct 670 ms 15728 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 16352 KB Output is correct
2 Correct 425 ms 15636 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 19500 KB Output is correct
2 Correct 433 ms 18416 KB Output is correct
3 Execution timed out 1099 ms 18884 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 18260 KB Output is correct
2 Execution timed out 1089 ms 17936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 21380 KB Output is correct
2 Correct 940 ms 19712 KB Output is correct
3 Execution timed out 1088 ms 19852 KB Time limit exceeded
4 Halted 0 ms 0 KB -