제출 #440234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440234		DanerZein	분수 공원 (IOI21_parks)	C++17	0 / 100	23 ms	19872 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX_N=2e5+10;
vector<vi> G;
int pa[MAX_N],tam[MAX_N];
bool vis[MAX_N];
vector<ii> ox[MAX_N],oy[MAX_N];
void init(int n){
  for(int i=0;i<n;i++){
    pa[i]=i; tam[i]=1;
  }
}
int findset(int i){
  if(pa[i]==i) return i;
  return pa[i]=findset(pa[i]);
}
bool issameset(int i,int j){
  return findset(i)==findset(j);
}
void unionset(int i,int j){
  if(!issameset(i,j)){
    int u=findset(i),v=findset(j);
    pa[u]=v;
    tam[v]+=tam[u];
  }
}
bool orden(iii a,iii b){
  if(a.second.second==b.second.second){
    return a.second.first<b.second.first;
  }
  return a.second.second<b.second.second;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
  int n=x.size();
  G.clear(); G.resize(n+1);
  for(int i=0;i<MAX_N;i++){
    ox[i].clear(); oy[i].clear();
  }
  memset(vis,0,sizeof vis);

  init(n);
  for(int i=0;i<n;i++){
    ox[x[i]].push_back(ii(y[i],i));
    oy[y[i]].push_back(ii(x[i],i));
  }
  for(int i=0;i<MAX_N;i++){
    sort(ox[i].begin(),ox[i].end());
    sort(oy[i].begin(),oy[i].end());
  }
  vector<int> ru,rv,ra,rb;
  for(int i=0;i<MAX_N;i++){
    int a,b;
    for(int j=0;j<ox[i].size();j++){
      if(j+1!=ox[i].size() && ox[i][j+1].first-ox[i][j].first==2){
	a=ox[i][j+1].second; b=ox[i][j].second;
	//if(issameset(a,b)) continue;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
    for(int j=0;j<oy[i].size();j++){
      if(j+1!=oy[i].size() && oy[i][j+1].first-oy[i][j].first==2){
	a=oy[i][j+1].second; b=oy[i][j].second;
	//	if(issameset(a,b)) continue;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
  }
  if(tam[findset(0)]!=n) return 0;
  int id=-1;
  for(int i=0;i<n;i++){
    if(G[i].size()==1){
      id=i; break;
    }
  }
  queue<int> q; q.push(id);
  set<ii> ban; vis[id]=1;
  while(!q.empty()){
    int u; u=q.front();
    q.pop();
    int c=0;
    for(auto &v:G[u]){
      if(!vis[v]) c++;
    }
    while(c!=0){
      int id=-1;
      for(auto &v:G[u]){
	if(vis[v]) continue;
	id=v;
	int mid;
	if(x[u]==x[v]){
	  mid=(y[u]+y[v])/2;
	  if(ban.find(ii(x[u]+1,mid))!=ban.end() || ban.find(ii(x[u]-1,mid))!=ban.end()){
	    id=v; break;
	  }
	}
	else{
	  mid=(x[u]+x[v])/2;
	  if(ban.find(ii(mid,y[u]+1))!=ban.end() || ban.find(ii(mid,y[u]-1))!=ban.end()){
	    id=v; break;
	  }
	}
      }
      if(id==-1) break;
      vis[id]=1;
      int a,b,mid;
      if(x[u]==x[id]){
	mid=(y[u]+y[id])/2;
	if(ban.find(ii(x[u]-1,mid))==ban.end()){
	  a=x[u]-1; b=mid;
	}
	else{
	  a=x[u]+1; b=mid;
	}
      }
      else{
	mid=(x[u]+x[id])/2;
	if(ban.find(ii(mid,y[u]-1))==ban.end()){
	  a=mid; b=y[u]-1;
	}
	else{
	  a=mid; b=y[u]+1;

	}
      }
      ban.insert(ii(a,b));
      ru.push_back(u); rv.push_back(id);
      ra.push_back(a); rb.push_back(b);
      q.push(id);
      c--;
    }
  }
  build(ru,rv,ra,rb);
  return 1;
}

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

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int j=0;j<ox[i].size();j++){
      |                 ~^~~~~~~~~~~~~
parks.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |       if(j+1!=ox[i].size() && ox[i][j+1].first-ox[i][j].first==2){
      |          ~~~^~~~~~~~~~~~~~
parks.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int j=0;j<oy[i].size();j++){
      |                 ~^~~~~~~~~~~~~
parks.cpp:67:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |       if(j+1!=oy[i].size() && oy[i][j+1].first-oy[i][j].first==2){
      |          ~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30