제출 #70535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70535		KLPP	Collapse (JOI18_collapse)	C++14	5 / 100	15037 ms	19696 KiB

collapse

#include "collapse.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	int C=T.size();
	int Q=P.size();
	pair<pair<int,int>,int> arr[Q];
	for(int i=0;i<Q;i++){
		arr[i].first.first=W[i];
		arr[i].first.second=P[i];
		arr[i].second=i;
	}
	sort(arr,arr+Q);
	int pnt=0;
	vector<pair<int,bool> >nei[N];
	vector<pair<int,int> > ans ;
	for(int i=0;i<C;i++){
		if(T[i]==0){
			nei[X[i]].push_back(pair<int,bool>(Y[i],true));
			nei[Y[i]].push_back(pair<int,bool>(X[i],true));
		}else{
			for(int j=0;j<nei[X[i]].size();j++){
				if(nei[X[i]][j].first==Y[i]){
					nei[X[i]][j].second=false;
				}
			}for(int j=0;j<nei[Y[i]].size();j++){
				if(nei[Y[i]][j].first==X[i]){
					nei[Y[i]][j].second=false;
				}
			}
		}
		while(pnt<Q && arr[pnt].first.first==i){
			bool visited[N];
			for(int j=0;j<N;j++){
				visited[j]=false;
			}int CC=0;
			for(int strt=0;strt<N;strt++){
				if(!visited[strt]){
					visited[strt]=true;
					CC++;
					queue<int>q;
					q.push(strt);
					while(!q.empty()){
						int u=q.front();q.pop();
						for(int j=0;j<nei[u].size();j++){
							int v=nei[u][j].first;
if(nei[u][j].second && !visited[v] && !(arr[pnt].first.second>=v ^ arr[pnt].first.second>=u)){
	visited[v]=true;
	q.push(v);
}
						}
					}
				}
			}ans.push_back(pair<int,int>(arr[pnt].second,CC));
			pnt++;
		}
	}sort(ans.begin(),ans.end());
	vector<int> R;
	for(int i=0;i<Q;i++){
		R.push_back(ans[i].second);
	}
	return R;
}

컴파일 시 표준 에러 (stderr) 메시지

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<nei[X[i]].size();j++){
                ~^~~~~~~~~~~~~~~~~
collapse.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    }for(int j=0;j<nei[Y[i]].size();j++){
                 ~^~~~~~~~~~~~~~~~~
collapse.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j=0;j<nei[u].size();j++){
                   ~^~~~~~~~~~~~~~
collapse.cpp:58:62: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
 if(nei[u][j].second && !visited[v] && !(arr[pnt].first.second>=v ^ arr[pnt].first.second>=u)){
                                         ~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35