oj.uz

Submission #252867

# Submission time Handle Problem Language Result Execution time Memory
252867 2020-07-26T11:23:30 Z Halit Izlet (COI19_izlet) C++17
0 / 100
 2000 ms 36468 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e3;

int subtask, n, arr[N+5][N+5], anc[N+5], color[N+5];
vector<int> t[N+5];
bool vis[N+5];

void dfs(int b,int x, set<int> sz){
	if(vis[x])
		return;
	vis[x] = 1;

	while(arr[b][x] != sz.size() && sz.find(color[x]) != sz.end())
		color[x]++;	
	
	sz.insert(color[x]);	
	while(arr[b][x] != sz.size()){
		if(sz.find(color[x]) == sz.end()){
			color[x]++;
			continue;
		}
		sz.insert(color[x]);
		if(arr[b][x] != sz.size()){
			color[x]++;
			sz.erase(sz.find(color[x]-1));
		}
	}	
	for(int i = 0;i < t[x].size();i++){
		if( (anc[t[x][i]] != x) && (anc[x] != t[x][i])) 
			continue;
		
		dfs(b,t[x][i], sz);
	}	
}

int main(){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> subtask >> n;
	for(int i = 1;i <= n;i++)
		color[i] = 1;

	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			cin >> arr[i][j];
	for(int i = 1;i <= n;i++){
		for(int j = i+1;j <= n;j++){
			if((arr[i][j] <= 2) && ((arr[i][j] == 1) + (anc[j] == 0) ) ){
				anc[j] = i;
				t[i].push_back(j);
				t[j].push_back(i);
			}
		}
	}
	
	set<int> tmp;
	for(int i = 1;i <= n;i++){
		memset(vis,0, sizeof vis);
		dfs(i,i,tmp);
	}

	for(int i = 1;i <= n;i++)
		cout << color[i] << " \n"[i == n];
	
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < t[i].size();j++){
			if(anc[t[i][j]] != i)
				continue;
			cout << i << ' ' << t[i][j] << '\n';
		}
	} 
}

Compilation message

izlet.cpp: In function 'void dfs(int, int, std::set<int>)':
izlet.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(arr[b][x] != sz.size() && sz.find(color[x]) != sz.end())
        ~~~~~~~~~~^~~~~~~~~~~~
izlet.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(arr[b][x] != sz.size()){
        ~~~~~~~~~~^~~~~~~~~~~~
izlet.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(arr[b][x] != sz.size()){
      ~~~~~~~~~~^~~~~~~~~~~~
izlet.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < t[x].size();i++){
                ~~^~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j < t[i].size();j++){
                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Execution timed out 2068 ms 35832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 36468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Execution timed out 2068 ms 35832 KB Time limit exceeded
3 Halted 0 ms 0 KB -