結果
| 問題 | No.3482 Quod Erat Demonstrandum |
| コンテスト | |
| ユーザー |
 graph11463
|
| 提出日時 | 2026-03-27 21:34:01 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 472 ms / 2,000 ms |
| コード長 | 8,148 bytes |
| 記録 | |
| コンパイル時間 | 5,246 ms |
| コンパイル使用メモリ | 398,084 KB |
| 実行使用メモリ | 58,120 KB |
| 最終ジャッジ日時 | 2026-03-27 21:34:27 |
| 合計ジャッジ時間 | 22,648 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 45 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
#include <ranges>
using namespace std;
using namespace atcoder;
//loop
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
//vector
#define ALL(A) A.begin(), A.end()
#define RV(A) reverse(ALL(A))
#define RALL(A) A.rbegin(), A.rend()
#define SORT(A) sort(ALL(A))
#define RSORT(A) sort(RALL(A))
//input
template<class T> inline void input(T& a) { cin >> a; }
template<class T> inline void input_li(T& a) {for(auto &ob:a) cin >> ob;}
template<class... T> inline void input(T&... a) { ((cin >> a), ...); }
//output
#define Yes(bo) cout << ((bo) ? "Yes":"No") << endl
#define YES(bo) cout << ((bo) ? "YES":"NO") << endl
#define yes(bo) cout << ((bo) ? "yes":"no") << endl
#define Taka(bo) cout << ((bo) ? "Takahashi":"Aoki") << endl
//other
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define sz size
#define is insert
#define ps push
#define tp top
#define ft front
#define pp pop
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}
//const
#define I_MAX 2147483647
#define I_MIN -2147483647
#define UI_MAX 4294967295
#define LL_MAX 9223372036854775807
#define LL_MIN -9223372036854775808
#define ULL_MAX 18446744073709551615
//type
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using Pair = pair<ll,ll>;
using vll = vector<ll>;
using mint = modint998244353;
using mint1 = modint1000000007;
const ll Inf = 1LL << 60;
//debug
#ifdef _DEBUG
#define debug(x) cerr << "dbg_var : " << #x << ": " << x << endl
#define debug2(x,y) cerr << "dbg_var : " << #x << ": " << x << " "<< #y << ": " << y << endl
#define debug3(x,y,z) cerr << "dbg_var : " << #x << ": " << x << " "<< #y << ": " << y << " " << #z << ": " << z <<endl
#define debug_v(x) cerr << "dbg_vect: " << #x << ": "; for(auto v:x) cerr << v << " "; cerr << endl
#define debug_s(x) cerr << "dbg_set : " << #x << ": {"; for(auto v:x) cerr << v << ","; cerr << "}" << endl
#define debug_p(x) cerr << "dbg_pair: " << #x << "Fir: " << x.first << " Sec: " << x.second << endl
#define debug_m(x) cerr << "dbg_map : " << #x << ": "; for(auto Ite1:x)cerr << "key: " << Ite1.first << " : " << Ite1.second << ", "; cerr<< endl
#define debug_l() cerr << "======================================" << endl
#else
#define debug(x)
#define debug2(x,y)
#define debug3(x,y,z)
#define debug_v(x)
#define debug_s(x)
#define debug_p(x)
#define debug_m(x)
#define debug_l()
#endif
ll getSum(vector<ll> b) {ll res=0;for(auto v:b){res+=v;}return res;}
ll GCD(ll a, ll b) {if (b == 0) return a;else return GCD(b, a % b);}
ll LCM(ll a, ll b) {ll d=GCD(a,b);return (a/d)*(b/d)*d;}
/*zahyou to ka*/
bool poich(ll P,ll Q){return(0<=P&&P<Q);}
bool poich2(ll i,ll j,ll H,ll W){return(poich(j,W)&&poich(i,H));}
vector<Pair> dxy{{1,0},{-1,0},{0,1},{0,-1}};
//https://algo-logic.info/calc-pow/
ll dpow(ll x, ll n,ll mod) {
ll ret = 1;
while (n > 0) {
if (n & 1) ret = ret * x % mod;
x = x * x % mod;
n >>= 1;
}
return ret;
}
ll chd21(ll N,ll i,ll j){
return N*i+j;
}
Pair chd12(ll N,ll X){
return {X/N,X%N};
}
//input
template <class T>
void input_v(vector<T> &vec){
for(auto &v:vec)cin >> v;
}
vector<ll> MakePrime(long long MAX_N){
vector<long long> Isprime,Prime;
Isprime.resize(MAX_N+2,true);
Isprime[0]=false;
Isprime[1]=false;
for(long long i=2;i*i<=MAX_N;i++){
if(Isprime[i]){
for(long long j=i*i;j<=MAX_N;j+=i)Isprime[j]=false;
}
}
for(long long i=0;i<MAX_N;i++)if(Isprime[i])Prime.push_back(i);
return Prime;
}
template<class T>
struct comb{
public:
comb():comb(10000000){}
comb(ll N):A(N,1),B(N,1){
for(ll i=0;i<N;i++){
A[i+1]=A[i]*(i+1);
B[i+1]=1/A[i+1];
}
}
T nCk1(ll n,ll k){
if(n<0||k<0||n-k<0)return (T)0;
return A[n]*B[k]*B[n-k];
}
T nPk1(ll n,ll k){
if(n<0||k<0||n-k<0)return (T)0;
return A[n]*B[k];
}
T nCk2(ll n,ll k){
T res=1;
for(ll i=k+1;i<=n;i++){
res*=i;
}
for(ll i=0;i<=n-k;i++){
res/=i;
}
return res;
}
vector<T> A;
vector<T> B;
};
vector<array<ll,2>> totu_cover(vector<array<ll,2>> points){
vector<array<ll,2>> p=points;
sort(p.begin(),p.end());
ll N=p.size();
auto func=[&](bool bo){
stack<array<ll,2>> st;
queue<array<ll,2>> que;
ll k=2*bo-1;
for(ll i=N-1;i>=0;i--){
que.push(p[i]);
}
while(!que.empty()){
auto v=que.front();
if(st.size()<2){
st.push(v);
que.pop();
}else{
auto o=st.top();st.pop();
auto t=st.top();
auto[a,b]=t;
auto[c,d]=o;
auto[e,f]=v;
if((f-b)*(a-c)*k>(d-b)*(a-e)*k){
continue;
}else{
st.push(o);
st.push(v);
que.pop();
}
}
}
vector<array<ll,2>> res;
while(!st.empty()){
res.push_back(st.top());
st.pop();
}
return res;
};
auto v=func(1);
auto u=func(0);
ll vn=v.size(),un=u.size();
vector<array<ll,2>> ans;
set<array<ll,2>> cot;
for(ll i=vn-1;i>=0;i--){
ans.push_back(v[i]);
cot.insert(v[i]);
}
for(ll i=0;i<un;i++){
if(!cot.count(u[i])){
ans.push_back(u[i]);
}
cot.insert(u[i]);
}
return ans;
}
struct Edge{
Edge(ll t) : to(t){}
ll to;
};
struct WeightEdge{
public:
WeightEdge(ll t,ll c) : to(t),cost(c) {}
ll to,cost;
bool operator<(const WeightEdge &other)const{
return cost<other.cost;
}
bool operator>(const WeightEdge &other)const{
return cost>other.cost;
}
bool operator<=(const WeightEdge &other)const{
return cost<=other.cost;
}
bool operator>=(const WeightEdge &other)const{
return cost>=other.cost;
}
};
//Graph
struct Graph{
public:
Graph(int n,ll e=0) : graph(n),N(n){
}
void addedge(ll u,ll v){
graph[u].push_back(Edge(v));
}
int size(){
return N;
}
int jisuu(int p){
return graph[p].size();
}
ll N;
vector<vector<Edge>> graph;
};
struct WeightGraph{
public:
WeightGraph(int n,ll e=0) : graph(n),N(n){
}
void addedge(ll u,ll v,ll c){
graph[u].push_back(WeightEdge(v,c));
}
int size(){
return N;
}
int jisuu(int p){
return graph[p].size();
}
ll N;
vector<vector<WeightEdge>> graph;
};
vector<ll> normal_bfs(Graph graph,ll s=0){
vector<ll> dist(graph.size(),Inf);
dist[s]=0;
queue<ll> que;
que.push(s);
while(!que.empty()){
ll a=que.front();que.pop();
for(auto v:graph.graph[a]){
if(dist[v.to]==Inf){
dist[v.to]=dist[a]+1;
que.push(v.to);
}
}
}
return dist;
}
void solve(){
ll N,M;cin >> N >> M;
Graph graph(2*N);
for(ll i=0;i<M;i++){
ll a,b,c;cin >> a >> b >> c;
a--,b--;
if(c==1){
graph.addedge(a,b);
graph.addedge(b,a);
graph.addedge(a+N,b+N);
graph.addedge(b+N,a+N);
}else{
graph.addedge(a,b+N);
graph.addedge(b,a+N);
}
}
auto dist=normal_bfs(graph,0);
if(dist[2*N-1]!=Inf){
cout << "Different" << endl;
cout << dist[2*N-1] << endl;
}else
if(dist[N-1]!=Inf){
cout << "Same" << endl;
cout << dist[N-1] << endl;
}else{
cout << "Unknown" << endl;
}
}
int main(){
ll T=1;cin >> T;
while(T--){
solve();
}
return 0;
}