Submission #252742

#	Time	Username	Problem	Language	Result	Execution time	Memory
252742		Halit	Izlet (COI19_izlet)	C++17	18 / 100	1879 ms	55972 KiB

izlet

#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 used[N+5];

void dfs(int b,int x, int c, set<int> sz, bool vis[]){
	if(vis[x])
		return;
	vis[x] = 1;
	color[x] = c;
	sz.insert(c);
	for(int i = 0;i < t[x].size();i++){
		if( (anc[t[x][i]] != x) + (anc[x] != t[x][i]) == 2) 
			continue;
		
		if(arr[b][t[x][i]] > sz.size())
			dfs(b,t[x][i], c+1, sz, vis);
		else
			dfs(b,t[x][i], c, sz, vis);
	}	
}

int main(){
	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++)
		dfs(i,i,color[i],tmp,used);

	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 (stderr)

izlet.cpp: In function 'void dfs(int, int, int, std::set<int>, bool*)':
izlet.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < t[x].size();i++){
                ~~^~~~~~~~~~~~~
izlet.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(arr[b][t[x][i]] > sz.size())
      ~~~~~~~~~~~~~~~~^~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j < t[i].size();j++){
                 ~~^~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57