結果
| 問題 | No.3508 OR Mapping |
| コンテスト | |
| ユーザー |
 Ryan Shaw
|
| 提出日時 | 2026-04-18 00:09:08 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 379 ms / 2,000 ms |
| コード長 | 4,323 bytes |
| 記録 | |
| コンパイル時間 | 2,507 ms |
| コンパイル使用メモリ | 295,932 KB |
| 実行使用メモリ | 163,952 KB |
| 最終ジャッジ日時 | 2026-04-18 00:09:34 |
| 合計ジャッジ時間 | 18,836 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 65 |
コンパイルメッセージ
main.cpp: In function 'void initcatalan(long long int)':
main.cpp:85:59: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
85 | for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
| ~~~~~~~~^
main.cpp:85:24: note: within this loop
85 | for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
| ~^~~~~~~~~~~
ソースコード
#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
const int MOD = 998244353;//
const int FACTMAX = 2000005;//
const int CATALANMAX = 1000005;//
int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX];
int expo(int a, int b){
int res=1;
a%=MOD;
while (b){
if (b&1)res=(res*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return res;
}
int inv(int num){
return expo(num, MOD-2);
}
void initfact(){
fact[0]=1;
for (int i=1; i<FACTMAX; ++i)fact[i]=(fact[i-1]*i)%MOD;
invfact[FACTMAX-1]=inv(fact[FACTMAX-1]);
for (int i=FACTMAX-2; i>=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD;
}
int ncr(int n, int r){
if (n<r||r<0)return 0;
return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD;
}
int gcd(int a, int b){
while (b){
int t=a%b;
a=b;
b=t;
}
return a;
}
int lcm(int a, int b){
int temp=gcd(a, b);
a/=temp;
b/=temp;
return a*b*temp;
}
void initcatalan(int k){
cat[0]=1;
for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while (t--){
int n, m, k;
cin>>n>>m>>k;
vector<vector<int>> g(n), rg(n);
vector<pii> ed;
vector<int> self(n, 0);
for (int i=0; i<m; ++i){
int u, v;
cin>>u>>v;
--u, --v;
g[u].pb(v);
rg[v].pb(u);
ed.pb({u, v});
if (u==v)self[u]=1;
}
vector<int> vis(n, 0), reach={0};
vis[0]=1;
for (int i=0; i<(int)reach.size(); ++i){
int u=reach[i];
for (int v:g[u]){
if (!vis[v]){
vis[v]=1;
reach.pb(v);
}
}
}
if ((int)reach.size()!=n){
cout<<"No\n";
continue;
}
vector<int> ord;
fill(vis.begin(), vis.end(), 0);
for (int s=0; s<n; ++s){
if (vis[s])continue;
stack<pii> st;
st.push({s, 0});
vis[s]=1;
while (!st.empty()){
int u=st.top().fi;
int &i=st.top().se;
if (i<(int)g[u].size()){
int v=g[u][i++];
if (!vis[v]){
vis[v]=1;
st.push({v, 0});
}
}
else{
ord.pb(u);
st.pop();
}
}
}
vector<int> comp(n, -1);
vector<vector<int>> grp;
for (int i=n-1; i>=0; --i){
int s=ord[i];
if (comp[s]!=-1)continue;
int id=grp.size();
grp.pb({});
stack<int> st;
st.push(s);
comp[s]=id;
while (!st.empty()){
int u=st.top();
st.pop();
grp[id].pb(u);
for (int v:rg[u]){
if (comp[v]==-1){
comp[v]=id;
st.push(v);
}
}
}
}
int c=grp.size();
vector<pii> dag_ed;
for (auto [u, v]:ed){
u=comp[u], v=comp[v];
if (u!=v)dag_ed.pb({u, v});
}
sort(dag_ed.begin(), dag_ed.end());
dag_ed.erase(unique(dag_ed.begin(), dag_ed.end()), dag_ed.end());
vector<vector<int>> dag(c);
vector<int> in(c, 0);
for (auto [u, v]:dag_ed){
dag[u].pb(v);
++in[v];
}
queue<int> q;
for (int i=0; i<c; ++i){
if (!in[i])q.push(i);
}
vector<int> top;
bool ok=1;
while (!q.empty()){
if ((int)q.size()>1)ok=0;
int u=q.front();
q.pop();
top.pb(u);
for (int v:dag[u]){
--in[v];
if (!in[v])q.push(v);
}
}
if (!ok||top[0]!=comp[0]){
cout<<"No\n";
continue;
}
vector<int> typ(c, 0), col(n, -1);
for (int id=0; id<c; ++id){
if ((int)grp[id].size()==1&&!self[grp[id][0]])continue;
queue<int> qq;
int s=grp[id][0];
qq.push(s);
col[s]=0;
bool odd=0;
while (!qq.empty()&&!odd){
int u=qq.front();
qq.pop();
for (int v:g[u]){
if (comp[v]!=id)continue;
int want=col[u]^1;
if (col[v]==-1){
col[v]=want;
qq.push(v);
}
else if (col[v]!=want){
odd=1;
break;
}
}
}
typ[id]=(odd?1:2);
}
if (typ[comp[0]]!=1)ok=0;
for (int i=0; i<c; ++i){
int u=top[i];
if (typ[u]==2)ok=0;
if (i&&typ[top[i-1]]==0&&typ[u]==0)ok=0;
}
cout<<(ok?"Yes\n":"No\n");
}
}