oj.uz

답안 #237897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237897 2020-06-09T08:32:59 Z MrRobot_28 Plahte (COCI17_plahte) C++17
0 / 160
 492 ms 15132 KB 
#include<bits/stdc++.h>
using namespace std;
vector <pair <int, int> > x;
bool cmp(int a, int b)
{
	if(x[a].first == x[b].first)
	{
		return x[a].second < x[b].second;
	}
	return x[a].first < x[b].first;
}
vector <vector <int> > colors;
vector <vector <int> > g;
vector <int> p;
vector <int> ans;
set <int> dfs(int v)
{
	set <int> st;
	set <int> :: iterator it;
	for(int i = 0; i < (int)g[v].size(); i++)
	{
		set <int> st1 = dfs(g[v][i]);
		if(st1.size() > st.size())
		{
			for(it = st.begin(); it != st.end(); it++)
			{
				st1.insert(*it);
			}
			swap(st, st1);
		}
		else
		{
			for(it = st1.begin(); it != st1.end(); it++)
			{
				st.insert(*it);
			}
		}
	}
	for(int i = 0; i < (int)colors[v].size(); i++)
	{
		st.insert(colors[v][i]);
	}
	ans[v] = st.size();
	return st;
}
signed main() {
	int n, m;
	cin >> n >> m;
	ans.resize(n + 1, 0);
	g.resize(n + 1);
	p.resize(n, -1);
	colors.resize(n + 1);
	vector <pair <pair <int, int>, pair <int, int> > > mat(n);
	vector <pair <pair <int, int>, int> > scan;
	for(int i = 0; i < n; i++)
	{
		cin >> mat[i].first.first >> mat[i].first.second >> mat[i].second.first >> mat[i].second.second;
		scan.push_back({{mat[i].first.first, -1}, i});
		scan.push_back({{mat[i].second.first, 1}, i});
	}
	x.resize(m);
	vector <int> col(m);
	vector <int> ind(m);
	for(int i = 0; i < m; i++)
	{
		cin >> x[i].first >> x[i].second >> col[i];
		ind[i] = i;
	}
	sort(ind.begin(), ind.end(), cmp);
	sort(scan.begin(), scan.end());
	int j = 0;
	set <pair <int, int> > st;
	for(int i = 0; i < (int)ind.size(); i++)
	{
		while(j < (int)scan.size() && (scan[j].first.first < x[ind[i]].first || scan[j].first.first== x[ind[i]].first && scan[j].first.second == -1))
		{
			int it = scan[j].second;
			if(scan[j].first.second == 1)
			{
				st.erase({mat[it].second.second, it});
			}
			else
			{
				set <pair <int, int> > :: iterator it1;
				it1 = st.lower_bound({mat[it].second.second, 0});
				if(it1 != st.end() && mat[it1 ->second].first.second <= mat[it].first.second)
				{
					p[it] = it1 -> second;
					g[it1 -> second].push_back(it);
				}
				st.insert({mat[it].second.second, it});
			}
			j++;
		}
		set <pair<int, int> > :: iterator it;
		it = st.lower_bound({x[ind[i]].second, 0});
		if(it != st.end() && mat[it -> second].first.second <= x[ind[i]].second)
		{
			colors[it -> second].push_back(col[ind[i]]);
		}
	}
	while(j < (int)scan.size()){
		int it = scan[j].second;
			if(scan[j].first.second == 1)
			{
				st.erase({mat[it].second.second, it});
			}
			else
			{
				set <pair <int, int> > :: iterator it1;
				it1 = st.lower_bound({mat[it].second.second, 0});
				if(it1 != st.end() && mat[it1 ->second].first.second <= mat[it].first.second)
				{
					p[it] = it1 -> second;
					g[it1 -> second].push_back(it);
				}
				st.insert({mat[it].second.second, it});
			}
			j++;
	}
	for(int i = 0; i < n; i++)
	{
		if(p[i] == -1)
		{
			g[n].push_back(i);
		}
	}
	dfs(n);
	for(int i = 0; i < n; i++){
		cout << ans[i] << "\n";
	}
	return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:75:113: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while(j < (int)scan.size() && (scan[j].first.first < x[ind[i]].first || scan[j].first.first== x[ind[i]].first && scan[j].first.second == -1))

Subtask #1
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 138 ms 5104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 158 ms 6256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 272 ms 9972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 440 ms 15132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 492 ms 14644 KB Output isn't correct
2 Halted 0 ms 0 KB -