oj.uz

Submission #1041622

# Submission time Handle Problem Language Result Execution time Memory
1041622 2024-08-02T06:24:21 Z Muhammad_Aneeq Izlet (COI19_izlet) C++17
43 / 100
 637 ms 74320 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
int const N=3e3+10;
int par[N]={};
bool vis[N][N]={};
vector<int>mem[N]={};
vector<int>nei[N]={};
int a[N][N]={};
int an[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;
}
set<int>s;
map<int,int>cnt;
void dfs(int u,int roo=-1,int v=-1)
{
	if (roo==-1)
		roo=u;
	if (a[roo][u]==s.size())
	{
		an[u]=an[roo];
	}
	s.insert(an[u]);
	cnt[an[u]]++;
	for (auto i:nei[u])
	{
		if (i!=v)
			dfs(i,roo,u);
	}
	cnt[an[u]]--;
	if (cnt[an[u]]==0)
		s.erase(an[u]);
}
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;
		return;
	}
	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]={};
			}
		}
	}
	vector<int>z;
	for (int i=1;i<n;i++)
		if (root(i)==i)
			z.push_back(i);
	vector<int>f;
	f.push_back(0);
	vector<pair<int,int>>g;
	while (z.size())
	{
		vector<int>g,x;
		for (auto i:z)
		{
			bool w=0;
			for (auto j:f)		
			{
				if (a[i][j]==2)
				{
					w=1;
					ans.push_back({i,j});
					nei[i].push_back(j);
					nei[j].push_back(i);
					break;
				}
			}
			if (w==0)
				g.push_back(i);
			else
				x.push_back(i);
		}
		z=g;
		for (auto i:x)
			f.push_back(i);
	}
	for (auto i:f)
		an[i]=i+1;
	for (auto i:f)
	{
		s={},cnt.clear();
		dfs(i);
	}
	for (auto i:f)
	{
		for (auto j:mem[i])
			an[j]=an[i];
	}
	for (int i=0;i<n;i++)
		cout<<an[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 dfs(int, int, int)':
izlet.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  if (a[roo][u]==s.size())
      |      ~~~~~~~~~^~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 340 ms 38100 KB Output is correct
3 Correct 341 ms 37972 KB Output is correct
4 Correct 261 ms 37716 KB Output is correct
5 Correct 290 ms 37844 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 43856 KB Output is correct
2 Correct 294 ms 56144 KB Output is correct
3 Correct 400 ms 74076 KB Output is correct
4 Correct 373 ms 74320 KB Output is correct
5 Correct 296 ms 53492 KB Output is correct
6 Correct 299 ms 62032 KB Output is correct
7 Correct 224 ms 52824 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 340 ms 38100 KB Output is correct
3 Correct 341 ms 37972 KB Output is correct
4 Correct 261 ms 37716 KB Output is correct
5 Correct 290 ms 37844 KB Output is correct
6 Correct 285 ms 43856 KB Output is correct
7 Correct 294 ms 56144 KB Output is correct
8 Correct 400 ms 74076 KB Output is correct
9 Correct 373 ms 74320 KB Output is correct
10 Correct 296 ms 53492 KB Output is correct
11 Correct 299 ms 62032 KB Output is correct
12 Correct 224 ms 52824 KB Output is correct
13 Incorrect 637 ms 54456 KB Output isn't correct
14 Halted 0 ms 0 KB -