oj.uz

답안 #144381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144381 2019-08-16T19:04:22 Z arayi Izlet (COI19_izlet) C++17
43 / 100
 949 ms 40484 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];
int get_parent(int x)
{
	if (p[x] == x) return x;
	return p[x] = get_parent(p[x]);
}
bool col[3010];
void dfs(int v)
{
	col[v] = true;
	for (auto p : g[v])
	{
		if (!col[p])
		{
			cout << v + 1 << " " << p + 1 << endl;
			dfs(p);
		}
	}
}
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];
		}
	}
	if (t == 1)
	{
		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;
					g[i].PB(j);
					g[j].PB(i);
				}
		pat[0] = 1;
		for (int i = 0; i < g[0].size(); i++) pat[g[0][i]] = 1;
		for (int i = 0; i < n; i++)
		{
			if (a[0][i] == 2)
			{
				if (get_parent(0) == get_parent(i)) continue;
				pat[i] = 2;	
				for (int j = 0; j < g[i].size(); j++) pat[g[i][j]] = 2;
				g[0].PB(i);
				g[i].PB(0);
				p[i] = 0;
			}
		}
		for (int i = 0; i < n; i++)
		{
			cout << pat[i] << " ";
		}
		cout << endl;
		dfs(0);
	}
	if (t == 2) {
		pat[0] = 1;
		sm = 2;
		for (int i = 1; i < n; i++)
		{
			if (a[0][i] > a[0][i - 1])
			{
				pat[i] = sm;
				sm++;
			}
			else
			{
				set <int> ss;
				for (int j = i - 1; j >= 0; j--)
				{
					ss.insert(pat[j]);
					if (a[i][j] == a[i][j + 1] && a[i][j] == ss.size())
					{
						//	cout << i << " " << j << " " << a[i][j] << endl;
						pat[i] = pat[j];
						break;
					}
				}
			}
		}
		for (int i = 0; i < n; i++)
		{
			cout << pat[i] << " ";
		}
		cout << endl;
		for (int i = 0; i < n - 1; i++)
		{
			cout << i + 1 << " " << i + 2 << endl;
		}
	}
	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:146:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < g[0].size(); i++) pat[g[0][i]] = 1;
                   ~~^~~~~~~~~~~~~
izlet.cpp:153:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < g[i].size(); j++) pat[g[i][j]] = 2;
                     ~~^~~~~~~~~~~~~
izlet.cpp:182:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (a[i][j] == a[i][j + 1] && a[i][j] == ss.size())
                                    ~~~~~~~~^~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 609 ms 35908 KB Output is correct
3 Correct 615 ms 36056 KB Output is correct
4 Correct 614 ms 37244 KB Output is correct
5 Correct 615 ms 38460 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 613 ms 35816 KB Output is correct
2 Correct 606 ms 40484 KB Output is correct
3 Correct 949 ms 40484 KB Output is correct
4 Correct 824 ms 40452 KB Output is correct
5 Correct 605 ms 40376 KB Output is correct
6 Correct 703 ms 40132 KB Output is correct
7 Correct 542 ms 35236 KB Output is correct

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 609 ms 35908 KB Output is correct
3 Correct 615 ms 36056 KB Output is correct
4 Correct 614 ms 37244 KB Output is correct
5 Correct 615 ms 38460 KB Output is correct
6 Correct 613 ms 35816 KB Output is correct
7 Correct 606 ms 40484 KB Output is correct
8 Correct 949 ms 40484 KB Output is correct
9 Correct 824 ms 40452 KB Output is correct
10 Correct 605 ms 40376 KB Output is correct
11 Correct 703 ms 40132 KB Output is correct
12 Correct 542 ms 35236 KB Output is correct
13 Incorrect 618 ms 37884 KB Unexpected end of file - int32 expected
14 Halted 0 ms 0 KB -