oj.uz

Submission #651975

# Submission time Handle Problem Language Result Execution time Memory
651975 2022-10-20T22:15:15 Z ziduo Potemkin cycle (CEOI15_indcyc) Java 11
70 / 100
 1000 ms 20344 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<>();
	    int[] dist = new int[n];
	    for(int i=0; i<n; i++)for(int j: edges[i]) {
	    	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 121 ms 10500 KB Output is correct
2 Correct 62 ms 8320 KB Output is correct
3 Correct 59 ms 8400 KB Output is correct
4 Correct 58 ms 8528 KB Output is correct
5 Correct 64 ms 8152 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 10220 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 10584 KB Output is correct
2 Correct 59 ms 8392 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 10316 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 14328 KB Output is correct
2 Correct 161 ms 14708 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 15360 KB Output is correct
2 Correct 268 ms 16080 KB Output is correct
3 Correct 346 ms 16284 KB Output is correct
4 Correct 714 ms 15564 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 16320 KB Output is correct
2 Correct 406 ms 15424 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 19444 KB Output is correct
2 Correct 471 ms 18364 KB Output is correct
3 Execution timed out 1089 ms 18464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 20344 KB Output is correct
2 Correct 964 ms 18936 KB Output is correct
3 Execution timed out 1078 ms 19068 KB Time limit exceeded
4 Halted 0 ms 0 KB -