oj.uz

Submission #144540

# Submission time Handle Problem Language Result Execution time Memory
144540 2019-08-17T05:47:19 Z arayi Izlet (COI19_izlet) C++17
100 / 100
 872 ms 86008 KB 
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#define fr first
#define sc second
#define MP make_pair
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
using namespace std;

lli gcd(lli a, lli b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
lli cg(lli n) {
	return n ^ (n >> 1);
}
lli SUM(lli a)
{
	return (a * (a + 1) / 2);
}
bool CAN(int x, int y, int n, int m)
{
	if (x >= 0 && y >= 0 && x < n && y < m)
	{
		return true;
	}
	return false;
}
double her(double x1, double y1, double x2, double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
string strsum(string a, string b)
{
	int p = 0;
	string c;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	if (b.length() < a.length())
	{
		for (int i = b.length(); i < a.length(); i++)
		{
			b += "0";
		}
	}
	else
	{
		for (int i = a.length(); i < b.length(); i++)
		{
			a += "0";
		}
	}

	a += "0", b += "0";
	for (int i = 0; i < a.length(); i++)
	{
		c += (a[i] - '0' + b[i] - '0' + p) % 10 + '0';
		p = (a[i] + b[i] - '0' - '0' + p) / 10;
	}
	if (c[c.length() - 1] == '0') c.erase(c.length() - 1, 1);
	reverse(c.begin(), c.end());
	return c;
}
string strmin(string a, string b)
{
	if (a.length() > b.length()) return b;
	if (b.length() > a.length()) return a;
	for (int i = 0; i < a.length(); i++)
	{
		if (a[i] > b[i]) return b;
		if (b[i] > a[i]) return a;
	}
	return a;
}

char vow[] = { 'a', 'e', 'i', 'o', 'u' };
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };



const int N = 1e6 + 30;
const lli mod = 998244353;

int n, t;
int a[3010][3010], pat[3010], sm, p[3010];
vector <int> g[3010], g1[3010], g2[3010];
int get_parent(int x)
{
	if (p[x] == x) return x;
	return p[x] = get_parent(p[x]);
}
bool col[3010], col2[3010];
int par[3010];
void maq()
{
	for (int i = 0; i < n; i++)
	{
		col2[i] = false;
	}
}
void dfs(int v)
{
	col[v] = true;
	for (auto t : g1[v])
	{
		if (!col[t] && get_parent(v) != get_parent(t))
		{
			p[get_parent(t)] = v;
			g[v].PB(t);
			g[t].PB(v);
			dfs(t);
		}
	}
}
int sk;
void dfs2(int k, int v)
{
	col2[v] = true;
	if (pat[k]) return;
	if (a[sk][v] == a[k][v])
	{
		//cout << a[sk][v] << " " << a[k][v] << endl;
		pat[k] = pat[v];
		for(auto p1 : g2[k])
		{
			pat[p1] = pat[v];
		}
		return;
	}
	for(auto p : g[v])
	{
		if (pat[p] && !col2[p])
		{
			dfs2(k, p);
		}
	}
}
void dfs1(int v)
{
	for (auto p : g[v])
	{
		if (!pat[p])
		{
			//cout << p << " ";
			sk = v;
			dfs2(p, v);
			maq();
			if (!pat[p])
			{
				pat[p] = sm++;
				for (int p1 : g2[p])
					pat[p1] = pat[p];
			}
			//cout << pat[p] << endl;
			dfs1(p);

		}
	}
}
bool col1[3010];
void dfs3(int v)
{
	col1[v] = true;
	for (auto p : g2[v]) cout << v + 1 << " " << p + 1 << endl;
	for (auto p : g[v])
	{
		if (!col1[p])
		{
			cout << v + 1 << " " << p + 1 << endl;
			dfs3(p);
		}
	}
	//col1[v] = false;
}
int main()
{
	fastio;
	//freopen("c.in", "r", stdin);
	cin >> t >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}
	}
	
	for (int i = 0; i < n; i++) p[i] = i;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (a[i][j] == 1)
			{
				p[j] = i;
				g2[i].PB(j);
				g2[j].PB(i);
			}
	pat[0] = 1;
	sm = 2;
	for (int i = 0; i < g2[0].size(); i++) pat[g2[0][i]] = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (a[i][j] == 2)
			{
				g1[i].PB(j);
				g1[j].PB(i);
			}
		}
	}
	dfs(0);
	//dfs3(0);
	dfs1(0);
	for (int i = 0; i < n; i++)
	{
		cout << pat[i] << " ";
	}
	cout << endl;
	dfs3(0);
	return 0;
}

Compilation message

izlet.cpp: In function 'std::__cxx11::string strsum(std::__cxx11::string, std::__cxx11::string)':
izlet.cpp:57:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = b.length(); i < a.length(); i++)
                            ~~^~~~~~~~~~~~
izlet.cpp:64:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = a.length(); i < b.length(); i++)
                            ~~^~~~~~~~~~~~
izlet.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.length(); i++)
                  ~~^~~~~~~~~~~~
izlet.cpp: In function 'std::__cxx11::string strmin(std::__cxx11::string, std::__cxx11::string)':
izlet.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.length(); i++)
                  ~~^~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:216:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g2[0].size(); i++) pat[g2[0][i]] = 1;
                  ~~^~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 789 ms 84176 KB Output is correct
3 Correct 802 ms 84296 KB Output is correct
4 Correct 804 ms 85752 KB Output is correct
5 Correct 813 ms 86008 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 36356 KB Output is correct
2 Correct 818 ms 84116 KB Output is correct
3 Correct 867 ms 36460 KB Output is correct
4 Correct 872 ms 36412 KB Output is correct
5 Correct 653 ms 44888 KB Output is correct
6 Correct 696 ms 37436 KB Output is correct
7 Correct 529 ms 31848 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 789 ms 84176 KB Output is correct
3 Correct 802 ms 84296 KB Output is correct
4 Correct 804 ms 85752 KB Output is correct
5 Correct 813 ms 86008 KB Output is correct
6 Correct 637 ms 36356 KB Output is correct
7 Correct 818 ms 84116 KB Output is correct
8 Correct 867 ms 36460 KB Output is correct
9 Correct 872 ms 36412 KB Output is correct
10 Correct 653 ms 44888 KB Output is correct
11 Correct 696 ms 37436 KB Output is correct
12 Correct 529 ms 31848 KB Output is correct
13 Correct 663 ms 36164 KB Output is correct
14 Correct 778 ms 41248 KB Output is correct
15 Correct 668 ms 54376 KB Output is correct
16 Correct 765 ms 46928 KB Output is correct
17 Correct 754 ms 45856 KB Output is correct
18 Correct 643 ms 46024 KB Output is correct
19 Correct 734 ms 62708 KB Output is correct
20 Correct 677 ms 61432 KB Output is correct
21 Correct 705 ms 62984 KB Output is correct
22 Correct 666 ms 50652 KB Output is correct
23 Correct 687 ms 50008 KB Output is correct
24 Correct 739 ms 41512 KB Output is correct
25 Correct 651 ms 52728 KB Output is correct