結果

問題 No.1023 Cyclic Tour
ユーザー maroon_kurimaroon_kuri
提出日時 2020-04-10 22:32:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 88 ms / 2,000 ms
コード長 5,195 bytes
コンパイル時間 2,047 ms
コンパイル使用メモリ 185,664 KB
実行使用メモリ 19,980 KB
最終ジャッジ日時 2024-09-15 21:01:21
合計ジャッジ時間 7,317 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 28 ms
5,376 KB
testcase_05 AC 28 ms
5,376 KB
testcase_06 AC 30 ms
5,376 KB
testcase_07 AC 29 ms
5,376 KB
testcase_08 AC 37 ms
9,892 KB
testcase_09 AC 49 ms
15,724 KB
testcase_10 AC 47 ms
15,744 KB
testcase_11 AC 51 ms
16,452 KB
testcase_12 AC 52 ms
17,764 KB
testcase_13 AC 48 ms
16,904 KB
testcase_14 AC 48 ms
16,760 KB
testcase_15 AC 49 ms
17,296 KB
testcase_16 AC 83 ms
19,456 KB
testcase_17 AC 80 ms
19,592 KB
testcase_18 AC 80 ms
18,932 KB
testcase_19 AC 78 ms
18,688 KB
testcase_20 AC 63 ms
15,804 KB
testcase_21 AC 64 ms
16,024 KB
testcase_22 AC 74 ms
17,132 KB
testcase_23 AC 78 ms
17,744 KB
testcase_24 AC 87 ms
19,980 KB
testcase_25 AC 65 ms
15,952 KB
testcase_26 AC 63 ms
16,044 KB
testcase_27 AC 63 ms
15,344 KB
testcase_28 AC 86 ms
19,144 KB
testcase_29 AC 88 ms
19,916 KB
testcase_30 AC 87 ms
19,464 KB
testcase_31 AC 81 ms
18,560 KB
testcase_32 AC 80 ms
18,560 KB
testcase_33 AC 84 ms
19,080 KB
testcase_34 AC 22 ms
5,868 KB
testcase_35 AC 48 ms
6,872 KB
testcase_36 AC 68 ms
16,464 KB
testcase_37 AC 75 ms
18,000 KB
testcase_38 AC 80 ms
19,148 KB
testcase_39 AC 78 ms
17,592 KB
testcase_40 AC 80 ms
17,848 KB
testcase_41 AC 78 ms
17,848 KB
testcase_42 AC 57 ms
9,432 KB
testcase_43 AC 57 ms
11,028 KB
testcase_44 AC 35 ms
11,888 KB
testcase_45 AC 60 ms
19,720 KB
testcase_46 AC 50 ms
17,928 KB
testcase_47 AC 33 ms
12,192 KB
testcase_48 AC 64 ms
16,384 KB
testcase_49 AC 66 ms
16,136 KB
testcase_50 AC 63 ms
16,008 KB
testcase_51 AC 55 ms
8,968 KB
testcase_52 AC 58 ms
10,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
return os<<"{"<<p.a<<","<<p.b<<"}";
}
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
os<<"{";
for(auto e:v)os<<e<<",";
return os<<"}";
}
#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
os<<t<<" ";
dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif
using uint=unsigned;
using ull=unsigned long long;
template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
return os<<vc<t>(all(a));
}
template<int i,class T>
void print_tuple(ostream&,const T&){
}
template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
if(i)os<<",";
os<<get<i>(t);
print_tuple<i+1,T,Args...>(os,t);
}
template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
os<<"{";
print_tuple<0,tuple<Args...>,Args...>(os,t);
return os<<"}";
}
template<class t>
void print(t x,int suc=1){
cout<<x;
if(suc==1)
cout<<"\n";
if(suc==2)
cout<<" ";
}
ll read(){
ll i;
cin>>i;
return i;
}
vi readvi(int n,int off=0){
vi v(n);
rep(i,n)v[i]=read()+off;
return v;
}
template<class T>
void print(const vector<T>&v,int suc=1){
rep(i,v.size())
print(v[i],i==int(v.size())-1?suc:2);
}
string readString(){
string s;
cin>>s;
return s;
}
template<class T>
T sq(const T& t){
return t*t;
}
//#define CAPITAL
void yes(bool ex=true){
#ifdef CAPITAL
cout<<"YES"<<"\n";
#else
cout<<"Yes"<<"\n";
#endif
if(ex)exit(0);
}
void no(bool ex=true){
#ifdef CAPITAL
cout<<"NO"<<"\n";
#else
cout<<"No"<<"\n";
#endif
if(ex)exit(0);
}
void possible(bool ex=true){
#ifdef CAPITAL
cout<<"POSSIBLE"<<"\n";
#else
cout<<"Possible"<<"\n";
#endif
if(ex)exit(0);
}
void impossible(bool ex=true){
#ifdef CAPITAL
cout<<"IMPOSSIBLE"<<"\n";
#else
cout<<"Impossible"<<"\n";
#endif
if(ex)exit(0);
}
constexpr ll ten(int n){
return n==0?1:ten(n-1)*10;
}
const ll infLL=LLONG_MAX/3;
#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif
int topbit(signed t){
return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
return __builtin_popcount(t);
}
int popcount(ll t){
return __builtin_popcountll(t);
}
bool ispow2(int i){
return i&&(i&-i)==i;
}
ll mask(int i){
return (ll(1)<<i)-1;
}
bool inc(int a,int b,int c){
return a<=b&&b<=c;
}
template<class t> void mkuni(vc<t>&v){
sort(all(v));
v.erase(unique(all(v)),v.ed);
}
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
template<class t>
void myshuffle(vc<t>&a){
rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}
template<class t>
int lwb(const vc<t>&v,const t&a){
return lower_bound(all(v),a)-v.bg;
}
//VERIFY: yosupo
//KUPC2017J
//AOJDSL1A
//without rank
struct unionfind{
vi p,s;
int c;
unionfind(int n):p(n,-1),s(n,1),c(n){}
int find(int a){
return p[a]==-1?a:(p[a]=find(p[a]));
}
//set b to a child of a
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b)return false;
p[b]=a;
s[a]+=s[b];
c--;
return true;
}
bool same(int a,int b){
return find(a)==find(b);
}
int sz(int a){
return s[find(a)];
}
};
//AOJGRL4B
template<class t>
vi toposort(vvc<t> g){
int n=g.size();
vi a(n);
rep(i,n)for(auto e:g[i])
a[e]++;
queue<int> q;
rep(i,n)if(a[i]==0)
q.push(i);
vi res;
rep(i,n){
if(q.empty())return {};
int v=q.front();q.pop();
res.pb(v);
for(auto e:g[v])
if(--a[e]==0)
q.push(e);
}
return res;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
int n,m;cin>>n>>m;
vc<pi> es;
unionfind uf(n);
rep(_,m){
int a,b,c;cin>>a>>b>>c;
a--;b--;
if(c==1){
if(!uf.unite(a,b))
yes();
}else{
es.eb(a,b);
}
}
vvc<int> g(n);
for(auto e:es){
int a,b;tie(a,b)=e;
a=uf.find(a),b=uf.find(b);
if(a==b)yes();
g[a].pb(b);
}
auto ans=toposort(g);
if(si(ans))no();
else yes();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0