結果

問題 No.3103 Butterfly Effect
ユーザー Tourmaline
提出日時 2025-04-11 23:36:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,051 ms / 5,000 ms
コード長 4,875 bytes
コンパイル時間 6,163 ms
コンパイル使用メモリ 333,976 KB
実行使用メモリ 93,004 KB
最終ジャッジ日時 2025-04-11 23:37:19
合計ジャッジ時間 42,755 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll=long long;
using LL=__int128;
using ld=long double;
using uint=unsigned int;
using ull=unsigned long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vvc=vector<vc<T>>;
template<typename T> using vvvc=vector<vvc<T>>;
using vi=vc<int>;
using vvi=vvc<int>;
using vd=vc<ld>;
using vvd=vvc<ld>;
using vl=vc<ll>;
using vvl=vvc<ll>;
using vs=vc<string>;
using vp=vc<pll>;
using vvp=vvc<pll>;

#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll _=0;_<ll(n);_++)
#define rep2(i,n) for(ll i=0;i<ll(n);i++)
#define rep3(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define rep(...) overload3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll _=ll(n);_--;)
#define rrep2(i,n) for(ll i=ll(n);i--;)
#define rrep3(i,a,b) for(ll i=ll(b);i-->ll(a);)
#define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)

#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

template<int m>
ostream& operator<<(ostream& os,static_modint<m> v){
	os<<v.val();
	return os;
}
istream& operator>>(istream& is,__int128& v){
    string s;
    is>>s;
    v=0;
	rep(i,s.size())if(isdigit(s[i])) v=v*10+s[i]-'0';
	if(s[0]=='-') v*=-1;
    return is;
}
ostream& operator<<(ostream& os,__int128 v){
	ostream::sentry s(os);
	if(s){
		__uint128_t t=v<0?-v:v;
		char buf[128];
		char* d=end(buf);
		do{
			d--;
			*d="0123456789"[t%10];
			t/=10;
		}while(t);
		if(v<0){
			d--;
			*d='-';
		}
		int len=end(buf)-d;
		if(os.rdbuf()->sputn(d,len)!=len) os.setstate(ios_base::badbit);
	}
	return os;
}
template<typename S,typename T>
ostream& operator<<(ostream& os,pair<S,T> a){
	os<<a.first<<' '<<a.second;
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<T> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<' '<<a[i];
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<vector<T>> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<endl<<a[i];
	return os;
}
void output(auto x){cout<<x<<endl;}
template<typename T>
void output(vector<T> a,bool next_line=0){
	if(next_line){
		for(auto x:a) output(x);
	}
	else cout<<a<<endl;
}

void debug(auto ...vs){
	((cout<<vs<<", "),...)<<endl;
}

void syosu(int x=15){cout<<fixed<<setprecision(x);}
void YN(bool x){cout<<(x?"Yes":"No")<<endl;}
void chmin(auto &x,auto y){if(x>y) x=y;}
void chmax(auto &x,auto y){if(x<y) x=y;}

template<typename T>
void read(vector<T> &a,int n,int off=0){
	a=vector<T>(n);
	for(auto &i:a){
		cin>>i;
		i-=off;
	}
}

void read(vs &a,int n){
	a=vs(n);
	for(auto &i:a) cin>>i;
}

template<typename T>
void read(vector<pair<T,T>> &a,int n,int off=0){
	a=vector<pair<T,T>>(n);
	for(auto &[x,y]:a){
		cin>>x>>y;
		x-=off,y-=off;
	}
}

template<typename T>
void read(vector<vector<T>> &a,int n,int m,int off=0){
	a=vector<vector<T>>(n,vector<T>(m));
	for(auto &i:a) for(auto &j:i){
		cin>>j;
		j-=off;
	}
}

template<typename T>
void readGraph(vector<vector<T>> &g,int n,int m,bool rv=1,int off=1){
	g=vector<vector<T>>(n);
	for(int i=0;i<m;i++){
		T u,v;
		cin>>u>>v;
		u-=off,v-=off;
		g[u].emplace_back(v);
		if(rv) g[v].emplace_back(u);
	}
}

template<typename T>
void readGraph(vector<vector<pair<T,T>>> &g,int n,int m,bool id=0,bool rv=1,int off=1){
	g=vector<vector<pair<T,T>>>(n);
	for(int i=0;i<m;i++){
		if(id){
			T u,v;
			cin>>u>>v;
			u-=off,v-=off;
			g[u].emplace_back(v,i);
			if(rv) g[v].emplace_back(u,i);
		}
		else{
			T u,v,w;
			cin>>u>>v>>w;
			u-=off,v-=off;
			g[u].emplace_back(v,w);
			if(rv) g[v].emplace_back(u,w);
		}
	}
}

string toBinary(ll x,ll n,bool rev=0){
	assert(0<=x&&x<1LL<<n);
	string s(n,'0');
	for(int i=0;i<n;i++) if(x&1LL<<i) s[n-i-1]='1';
	if(rev) reverse(s.begin(),s.end());
	return s;
}

constexpr ll inf=1<<30;
constexpr ll INF=1ll<<60;
const ld pi=acosl(-1);
constexpr ld eps=1e-9;
//constexpr ll mod=1e9+7;
constexpr ll mod=998244353;
constexpr int dx[9]={-1,0,1,0,1,1,-1,-1,0};
constexpr int dy[9]={0,1,0,-1,1,-1,1,-1,0};

using mint=static_modint<mod>;
using vm=vc<mint>;
using vvm=vvc<mint>;

void main2();

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll q=1;
//	cin>>q;
	while(q--) main2();
}

void main2(){
	ll n,q;
	cin>>n>>q;
	vl a(n,INF);
	a[0]=0;
	ll rs=1;
	auto update=[&](ll v,ll t){
		if(a[v]==INF) rs++;
		a[v]=t;
	};
	vc<priority_queue<pll>> que(n);
	auto f=[&](auto sf,ll v)->void
	{
		while(!que[v].empty()){
			auto [t,u]=que[v].top();
			if(t<min(a[v],a[u])) break;
			que[v].pop();
			if(a[v]<t&&t<a[u]){
				update(u,t);
				sf(sf,u);
			}
		}
	};
	rep(q){
		ll t,u,v;
		cin>>t>>u>>v;
		u--,v--;
		que[u].emplace(t,v);
		que[v].emplace(t,u);
		f(f,u);
		f(f,v);
		output(rs);
	}
}
0