結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー yimiya（いみや）
提出日時 2025-03-02 21:49:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,234 bytes
コンパイル時間 3,556 ms
コンパイル使用メモリ 301,708 KB
実行使用メモリ 21,832 KB
最終ジャッジ日時 2025-11-01 09:23:55
合計ジャッジ時間 14,188 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 55 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <random>
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i,n) for (ll i = 0;i < (ll)(n);i++)
#define Yes cout << "Yes" << "\n"// YESの短縮
#define No cout << "No" << "\n"// NOの短縮
#define rtr0 return(0)//return(0)の短縮
#define gyakugen(x) modpow(x,mod - 2,mod);
#define agyakugen(x) modpow(x,amod - 2,amod);
using namespace std;
using ll = long long;//63bit型整数型
using ld = long double;//doubleよりも長い値を保存できるもの
using ull = unsigned long long;//符号がない64bit型整数
ll mod = 998244353;
ll amod = 1000000007;
ll MINF = -5000000000000000000;
ll INF = 5000000000000000000;
ll BAD = -1;
vector<ll>tate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック
vector<ll>yoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック
vector<ll>eightx = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック
vector<ll>eighty = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック
vector<ll>hexsax = {0,1,1,0,-1,-1};
vector<ll>hexsay = {1,1,0,-1,-1,0};
//返り値は素数のリスト。
vector < bool > isprime;
vector < ll > Era(int n){//書き方 vector<ll>[] = Era(x); とやるとxまでの素数が出てくる。
	isprime.resize(n, true);
	vector < ll > res;
	isprime[0] = false;
	isprime[1] = false;
	for(ll i = 2; i < n; ++i) isprime[i] = true;
	for(ll i = 2; i < n; ++i) {
		if(isprime[i]) {
			res.push_back(i);
			for(ll j = i * 2; j < n; j += i) isprime[j] = false;
		}
	}
	return res;
}
//　　　　　　素数判定 21~35

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
//     モッドを使った累乗
int main(){
//B以上は基本詳細を書いておくと便利　A ＝ ooの値とか　見直す時に便利
// この問題の本質
ll N,M;
cin >> N >> M;
vector<vector<ll>>graph(N,vector<ll>(0));
for(ll i = 0;i<M;i++){
	ll u,v;
	cin >> u >> v;
	u--;
	v--;
	graph[u].push_back(v);
	graph[v].push_back(u);
}
ll L;
cin >> L;
vector<ll>pass(N,-1);
for(ll i = 0;i<L;i++){
	ll J,K;
	cin >> J >> K;
	J--;
	pass[J] = max(pass[J],K);
}
priority_queue<pair<ll,ll>>pq;
for(ll i = 0;i<N;i++)if(pass[i] != -1)pq.push({pass[i],i});
while(true){
	if(pq.empty())break;
	ll distance = pq.top().first;
	ll point = pq.top().second;
	pq.pop();
	for(ll i = 0;i<graph[point].size();i++){
		ll x = graph[point][i];
		if(pass[x] < distance - 1){
			pass[x] = distance - 1;
			pq.push({pass[x],x});
		}
	}
}
//cout << "A" << "\n";
vector<bool>visited(N);
queue<ll>BFS;
if(pass[0] == -1)BFS.push(0);
while(true){
	if(BFS.empty())break;
	ll point = BFS.front();
	BFS.pop();
	visited[point] = true;
	for(ll i = 0;i<graph[point].size();i++){
		ll x = graph[point][i];
		if(visited[x] != true && pass[x] == -1){
			BFS.push(x);
			visited[x] = true;
		}
	}
}
if(visited[N-1] == true)cout << "Yes" << "\n";
else cout << "No" << "\n";
}
0