結果

問題 No.3369 Find MyakuMyaku
コンテスト
ユーザー kotatsugame
提出日時 2025-11-17 21:27:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 221 ms / 2,000 ms
コード長 1,083 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 84,336 KB
実行使用メモリ 65,316 KB
最終ジャッジ日時 2025-11-17 21:27:36
合計ジャッジ時間 7,490 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:25: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   53 |                 for(auto[x,y]:P[i])add(x,y);
      |                         ^

ソースコード

diff # 

#include<iostream>
#include<set>
#include<vector>
#include<cassert>
#include<atcoder/dsu>
using namespace std;
int N,H,W;
set<int>S[1002];
vector<pair<int,int> >P[1000];
bool white[1002*1002];
const int d[5]={0,1,0,-1,0};
bool ans[1000];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>H>>W;
	H+=2;W+=2;
	for(int x=0;x<H;x++)for(int y=0;y<W;y++)S[x].insert(y);
	for(int i=0;i<N;i++)
	{
		int lx,rx,ly,ry;
		cin>>lx>>rx>>ly>>ry;
		rx++,ry++;
		for(int x=lx;x<rx;x++)
		{
			auto it=S[x].lower_bound(ly);
			while(it!=S[x].end()&&*it<ry)
			{
				P[i].push_back(make_pair(x,*it));
				it=S[x].erase(it);
			}
		}
	}
	int wc=0,w=-1;
	atcoder::dsu uf(H*W);
	auto add=[&](int x,int y){
		w=x*W+y;
		white[w]=true;
		wc++;
		for(int r=0;r<4;r++)
		{
			int tx=x+d[r],ty=y+d[r+1];
			if(tx<0||ty<0||tx>=H||ty>=W)continue;
			int id=tx*W+ty;
			if(white[id])uf.merge(w,id);
		}
	};
	for(int x=0;x<H;x++)for(int y:S[x])add(x,y);
	for(int i=N;i--;)
	{
		ans[i]=w!=-1&&uf.size(w)<wc;
		for(auto[x,y]:P[i])add(x,y);
	}
	for(int i=0;i<N;i++)cout<<(ans[i]?"Yes\n":"No\n");
}
0