oj.uz

Submission #252742

# Submission time Handle Problem Language Result Execution time Memory
252742 2020-07-26T08:10:22 Z Halit Izlet (COI19_izlet) C++17
18 / 100
 1879 ms 55972 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 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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1807 ms 53496 KB Output is correct
3 Correct 1849 ms 53624 KB Output is correct
4 Correct 1849 ms 54776 KB Output is correct
5 Correct 1852 ms 55972 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1879 ms 54412 KB Output isn't correct
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 Correct 1807 ms 53496 KB Output is correct
3 Correct 1849 ms 53624 KB Output is correct
4 Correct 1849 ms 54776 KB Output is correct
5 Correct 1852 ms 55972 KB Output is correct
6 Incorrect 1879 ms 54412 KB Output isn't correct
7 Halted 0 ms 0 KB -