oj.uz

Submission #1041514

# Submission time Handle Problem Language Result Execution time Memory
1041514 2024-08-02T05:02:22 Z vjudge1 Izlet (COI19_izlet) C++17
43 / 100
 366 ms 55964 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
using namespace std;
int const N=3e3+10;
int par[N]={};
bool vis[N][N]={};
vector<int>mem[N]={};
int a[N][N]={};
int root(int n)
{
	if (par[n]==n) return n;
	return (par[n]=root(par[n]));
}
bool merge_able(int c,int b)
{
	if (vis[c][b])
		return 0;
	vis[c][b]=1;
	for (auto i:mem[c])
	{
		for (auto j:mem[b])
		{
			int u=i,v=j;
			if (u>v)
				swap(u,v);
			if (a[u][v-1]!=a[u][v])
				return 0;
		}
	}
	return 1;
}
void merge(int a,int b)
{
	a=root(a);b=root(b);
	if (a==b)
		return;
	if (merge_able(a,b)==0)
		return ;
	for (auto i:mem[b])
		mem[a].push_back(i);
	mem[b]={};
	par[b]=a;
}
inline void solve()
{
	int subt;
	cin>>subt;
	int n;
	cin>>n;
	for (int i=0;i<n;i++)
		par[i]=i,mem[i].push_back(i);
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			cin>>a[i][j];
	if (subt==2)
	{
		for (int i=1;i<n;i++)
		{
			for (int j=0;j<n-i;j++)
			{
				merge(j,i+j);
			}
		}
		for (int i=0;i<n;i++)
			cout<<root(i)+1<<' ';
		cout<<endl;
		for (int i=1;i<n;i++)
			cout<<i<<' '<<i+1<<endl;
	}
	if (subt==1)
	{
		vector<vector<int>>ans;
		for (int i=0;i<n;i++)
		{
			for (int j=i+1;j<n;j++)
			{
				if (a[i][j]==1)
				{
					int a=i,b=j;
					a=root(a),b=root(b);
					if (a==b)
						continue;
					par[b]=a;
					ans.push_back({a,b});
					for (auto i:mem[b])
						mem[a].push_back(i);
					mem[b]={};
				}
			}
		}
		int an[n]={};
		vector<int>z;
		for (int i=0;i<n;i++)
			if (root(i)==i)
				z.push_back(i);
		for (int i=1;i<z.size();i++)
		{
			ans.push_back({z[i],z[0]});
			for (auto j:mem[z[i]])
				an[j]=2;
		}
		for (auto i:mem[z[0]])
			an[i]=1;
		for (auto i:an)
			cout<<i<<' ';
		cout<<endl;
		for (auto i:ans)
			cout<<i[0]+1<<' '<<i[1]+1<<endl;
	}
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Compilation message

izlet.cpp: In function 'void solve()':
izlet.cpp:102:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int i=1;i<z.size();i++)
      |                ~^~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 247 ms 51376 KB Output is correct
3 Correct 282 ms 51472 KB Output is correct
4 Correct 261 ms 51284 KB Output is correct
5 Correct 247 ms 51352 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 43860 KB Output is correct
2 Correct 272 ms 41960 KB Output is correct
3 Correct 366 ms 45136 KB Output is correct
4 Correct 363 ms 44784 KB Output is correct
5 Correct 277 ms 39760 KB Output is correct
6 Correct 294 ms 41476 KB Output is correct
7 Correct 277 ms 36948 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 247 ms 51376 KB Output is correct
3 Correct 282 ms 51472 KB Output is correct
4 Correct 261 ms 51284 KB Output is correct
5 Correct 247 ms 51352 KB Output is correct
6 Correct 266 ms 43860 KB Output is correct
7 Correct 272 ms 41960 KB Output is correct
8 Correct 366 ms 45136 KB Output is correct
9 Correct 363 ms 44784 KB Output is correct
10 Correct 277 ms 39760 KB Output is correct
11 Correct 294 ms 41476 KB Output is correct
12 Correct 277 ms 36948 KB Output is correct
13 Incorrect 267 ms 55964 KB Unexpected end of file - int32 expected
14 Halted 0 ms 0 KB -