oj.uz

Submission #37455

# Submission time Handle Problem Language Result Execution time Memory
37455 2017-12-25T14:45:02 Z IvanC Plahte (COCI17_plahte) C++14
32 / 160
 2000 ms 17244 KB 
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> trinca;
typedef pair<int,int> ii;
const int MAXN = 1e5 + 10;
int X1[MAXN],X2[MAXN],Y1[MAXN],Y2[MAXN],raiz[MAXN],resposta[MAXN],N;
int XC[MAXN],YC[MAXN],COR[MAXN],M;
vector<int> grafo[MAXN],armazenado[MAXN];
set<int> *conjunto[MAXN];
vector<trinca> sweep;
set<ii> ativos;
void dfs(int v){
	int mx = -1, big = -1;
	for(int u : grafo[v]){
		dfs(u);
		int szu = conjunto[u]->size();
		if(szu > mx){
			mx = szu;
			big = u;
		}
	}
	if(big == -1){
		conjunto[v] = new set<int>();
		for(int i : armazenado[v]) conjunto[v]->insert(i);
	}
	else{
		conjunto[v] = conjunto[big];
		for(int i : armazenado[v]) conjunto[v]->insert(i);
	}
	for(int u : grafo[v]){
		if(u == big) continue;
		for(set<int>::iterator it = conjunto[u]->begin();it != conjunto[u]->end();it++){
			conjunto[v]->insert(*it);
		}
	}
	resposta[v] = conjunto[v]->size();
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=N;i++){
		scanf("%d %d %d %d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
		raiz[i] = 1;
		sweep.push_back(make_tuple(X1[i],0,i));
		sweep.push_back(make_tuple(X2[i],2,i));
	}
	for(int i = 1;i<=M;i++){
		scanf("%d %d %d",&XC[i],&YC[i],&COR[i]);
		sweep.push_back(make_tuple(XC[i],1,i));
	}
	sort(sweep.begin(),sweep.end());
	for(int evento = 0;evento<sweep.size();evento++){
		int op = get<1>(sweep[evento]), idx = get<2>(sweep[evento]);
		if(op == 0){
			int last = -1;
			for(set<ii>::iterator it = ativos.begin();it != ativos.end();it++){
				int pai = (*it).second;
				if(Y1[pai] > Y1[idx]) break;
				if(Y1[pai] <= Y1[idx] && Y2[idx] <= Y2[pai]){
					last = pai;
				}
			}
			if(last != -1){
				raiz[idx] = 0;
				grafo[last].push_back(idx);
			}
			ativos.insert(ii(Y1[idx],idx));
		}
		else if(op == 1){
			int last = -1;
			for(set<ii>::iterator it = ativos.begin();it != ativos.end();it++){
				int pai = (*it).second;
				if(Y1[pai] > YC[idx]) break;
				if(Y1[pai] <= YC[idx] && YC[idx] <= Y2[pai]){
					last = pai;
				}
			}
			if(last != -1){
				armazenado[last].push_back(COR[idx]);
			}
		}
		else{
			ativos.erase(ii(Y1[idx],idx));
		}
	}
	for(int i = 1;i<=N;i++){
		if(raiz[i]) dfs(i);
	}
	for(int i = 1;i<=N;i++){
		printf("%d\n",resposta[i]);
	}
	return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:51:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int evento = 0;evento<sweep.size();evento++){
                           ^
plahte.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
plahte.cpp:41:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
                                                   ^
plahte.cpp:47:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&XC[i],&YC[i],&COR[i]);
                                          ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1553 ms 16188 KB Output is correct
2 Correct 309 ms 17244 KB Output is correct
3 Correct 0 ms 11008 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 14076 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 15700 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 15700 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 15700 KB Execution timed out
2 Halted 0 ms 0 KB -