提出 #24060381

ソースコード 拡げる

#line 1 "a.cpp"
#include<iostream>
#include<atcoder/modint>
#include<atcoder/dsu>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
#line 2 "/home/kotatsugame/library/math/matrix.cpp"
#include<cassert>
template<typename T>
struct Matrix{
	vector<vector<T> >dat;
	int N,M;//N x M matrix
	Matrix(){}
	Matrix(int N_):Matrix(N_,N_){}
	Matrix(int N_,int M_):N(N_),M(M_),dat(N_,vector<T>(M_)){}
	vector<T>&operator[](int i){return dat[i];}
	const vector<T>&operator[](int i)const{return dat[i];}
	static Matrix eye(int N)
	{
		Matrix res(N);
		for(int i=0;i<N;i++)res[i][i]=1;
		return res;
	}
	Matrix operator+(const Matrix&A)const
	{
		assert(N==A.N&&M==A.M);
		Matrix res(N,M);
		for(int i=0;i<N;i++)for(int j=0;j<M;j++)
			res[i][j]=dat[i][j]+A[i][j];
		return res;
	}
	Matrix operator-(const Matrix&A)const
	{
		assert(N==A.N&&M==A.M);
		Matrix res(N,M);
		for(int i=0;i<N;i++)for(int j=0;j<M;j++)
			res[i][j]=dat[i][j]-A[i][j];
		return res;
	}
	Matrix operator*(const Matrix&A)const
	{
		assert(M==A.N);
		Matrix res(N,A.M);
		for(int i=0;i<N;i++)for(int k=0;k<M;k++)for(int j=0;j<A.M;j++)
			res[i][j]+=dat[i][k]*A[k][j];
		return res;
	}
	Matrix pow(long long n)const
	{
		assert(N==M);
		Matrix a=*this,res=eye(N);
		for(;n;a=a*a,n>>=1)if(n&1)res=res*a;
		return res;
	}
	template<typename U>
	Matrix operator+(const U&A)const
	{
		Matrix res(N,M);
		for(int i=0;i<N;i++)for(int j=0;j<M;j++)
			res[i][j]=dat[i][j]+A;
		return res;
	}
	template<typename U>
	Matrix operator-(const U&A)const
	{
		Matrix res(N,M);
		for(int i=0;i<N;i++)for(int j=0;j<M;j++)
			res[i][j]=dat[i][j]-A;
		return res;
	}
	template<typename U>
	Matrix operator*(const U&A)const
	{
		Matrix res(N,M);
		for(int i=0;i<N;i++)for(int j=0;j<M;j++)
			res[i][j]=dat[i][j]*A;
		return res;
	}
	T det()const
	{
		assert(N==M);
		Matrix A=*this;
		T ret=1;
		for(int j=0;j<N;j++)
		{
			int id=-1;
			for(int i=j;i<N;i++)
			{
				if(A[i][j]!=0)
				{
					id=i;
					break;
				}
			}
			if(id==-1)return T(0);
			if(id!=j)
			{
				A[j].swap(A[id]);
				ret=-ret;
			}
			ret*=A[j][j];
			{
				const T a=1/A[j][j];
				for(int k=j+1;k<N;k++)A[j][k]*=a;
			}
			for(int i=j+1;i<N;i++)
			{
				const T a=A[i][j];
				for(int k=j+1;k<N;k++)A[i][k]-=A[j][k]*a;
			}
		}
		return ret;
	}
	int elimination()
	{
		int ret=0;
		for(int j=0;j<M;j++)
		{
			int id=-1;
			for(int i=ret;i<N;i++)
			{
				if(dat[i][j]!=0)
				{
					id=i;
					break;
				}
			}
			if(id==-1)continue;
			if(id!=ret)dat[ret].swap(dat[id]);
			{
				const T a=1/dat[ret][j];
				for(int k=j;k<M;k++)dat[ret][k]*=a;
			}
			for(int i=0;i<N;i++)
			{
				if(i==ret)continue;
				const T a=dat[i][j];
				for(int k=j;k<M;k++)dat[i][k]-=dat[ret][k]*a;
			}
			ret++;
		}
		return ret;
	}
};
#line 9 "a.cpp"
using mint=atcoder::modint1000000007;
using mat=Matrix<mint>;
int N,M;
main()
{
	cin>>N>>M;
	vector<pair<int,pair<int,int> > >E(M);
	for(int i=0;i<M;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		a--,b--;
		E[i]=make_pair(c,make_pair(a,b));
	}
	sort(E.begin(),E.end());
	atcoder::dsu P(N);
	int sum=0;
	mint way=1;
	for(int i=0;i<M;)
	{
		int j=i;
		vector<pair<int,int> >e;
		vector<int>v;
		while(j<M&&E[i].first==E[j].first)
		{
			int a=E[j].second.first,b=E[j].second.second;
			if(!P.same(a,b))
			{
				e.push_back(make_pair(P.leader(a),P.leader(b)));
				v.push_back(P.leader(a));
				v.push_back(P.leader(b));
			}
			j++;
		}
		while(i<j)
		{
			int a=E[i].second.first,b=E[i].second.second;
			if(!P.same(a,b))
			{
				P.merge(a,b);
				sum+=E[i].first;
			}
			i++;
		}
		if(!v.empty())
		{
			sort(v.begin(),v.end());
			v.erase(unique(v.begin(),v.end()),v.end());
			int root=v[0];
			set<int>vis;
			vis.insert(P.leader(root));
			for(int w:v)
			{
				int x=P.leader(w);
				if(vis.find(x)==vis.end())
				{
					vis.insert(x);
					e.push_back(make_pair(root,w));
				}
			}
			mat A(v.size()-1);
			for(pair<int,int>p:e)
			{
				int x=lower_bound(v.begin(),v.end(),p.first)-v.begin();
				int y=lower_bound(v.begin(),v.end(),p.second)-v.begin();
				if(x<v.size()-1)A[x][x]++;
				if(y<v.size()-1)A[y][y]++;
				if(x<v.size()-1&&y<v.size()-1)A[x][y]--,A[y][x]--;
			}
			way*=A.det();
		}
	}
	cout<<sum<<" "<<way.val()<<endl;
}

提出情報

提出日時
問題 D - 僕は友達が少ない
ユーザ kotatsugame
言語 C++ (GCC 9.2.1)
得点 100
コード長 4210 Byte
結果 AC
実行時間 274 ms
メモリ 4964 KiB

コンパイルエラー

a.cpp:12:6: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
a.cpp: In function ‘int main()’:
a.cpp:73:9: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
a.cpp:74:9: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
a.cpp:75:9: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
a.cpp:75:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
/home/kotatsugame/library/math/matrix.cpp: In instantiation of ‘Matrix<T>::Matrix(int, int) [with T = atcoder::static_modint<1000000007>]’:
/home/kotatsugame/library/math/matrix.cpp:8:29:   required from ‘Matrix<T>::Matrix(int) [with T = atcoder::static_modint<1000000007>]’
a.cpp:68:20:   required from here
/home/kotatsugame/library/math/matrix.cpp:6:8: warning: ‘Matrix<atcoder::static_modint<1000000007> >::M’ will be initialized after [-Wreorder]
/home/kotatsugame/library/math/matrix.cpp:5:20: warning:   ‘std::vector<std::vector<atcoder::static_modint<1000000007>, std::allocator<atcoder::static_modint<1000000007> > >, std::allocator<std::vector<atcoder::static_modint<1000000007>, std::allocator<atcoder::static_modint<1000000007> > > > > Matrix<atcoder::static_modint<1000000007> >::dat’ [-Wreorder]
/home/kotatsugame/library/math/matrix.cpp:9:2: warning:   when initialized here [-Wreorder]

ジャッジ結果

セット名 Sample SubScore1 SubScore2
得点 / 配点 0 / 0 10 / 10 90 / 90
結果
AC × 4
AC × 10
AC × 42
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
SubScore1 sub1_case_01.txt, sub1_case_02.txt, sub1_case_03.txt, sub1_case_04.txt, sub1_case_05.txt, sub1_case_06.txt, sub1_case_07.txt, sub1_case_08.txt, sub1_case_09.txt, sub1_case_10.txt
SubScore2 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sub1_case_01.txt, sub1_case_02.txt, sub1_case_03.txt, sub1_case_04.txt, sub1_case_05.txt, sub1_case_06.txt, sub1_case_07.txt, sub1_case_08.txt, sub1_case_09.txt, sub1_case_10.txt, sub2_case_01.txt, sub2_case_02.txt, sub2_case_03.txt, sub2_case_04.txt, sub2_case_05.txt, sub2_case_06.txt, sub2_case_07.txt, sub2_case_08.txt, sub2_case_09.txt, sub2_case_10.txt, sub2_case_11.txt, sub2_case_12.txt, sub2_case_13.txt, sub2_case_14.txt, sub2_case_15.txt, sub2_case_16.txt, sub2_case_17.txt, sub2_case_18.txt, sub2_case_19.txt, sub2_case_20.txt, sub2_case_21.txt, sub2_case_22.txt, sub2_case_23.txt, sub2_case_24.txt, sub2_case_25.txt, sub2_case_26.txt, sub2_case_27.txt, sub2_case_28.txt
ケース名 結果 実行時間 メモリ
sample_01.txt AC 10 ms 3492 KiB
sample_02.txt AC 5 ms 3624 KiB
sample_03.txt AC 2 ms 3572 KiB
sample_04.txt AC 2 ms 3580 KiB
sub1_case_01.txt AC 3 ms 3632 KiB
sub1_case_02.txt AC 3 ms 3520 KiB
sub1_case_03.txt AC 11 ms 3636 KiB
sub1_case_04.txt AC 70 ms 4596 KiB
sub1_case_05.txt AC 21 ms 3756 KiB
sub1_case_06.txt AC 15 ms 3592 KiB
sub1_case_07.txt AC 74 ms 4508 KiB
sub1_case_08.txt AC 76 ms 4596 KiB
sub1_case_09.txt AC 66 ms 4176 KiB
sub1_case_10.txt AC 58 ms 4248 KiB
sub2_case_01.txt AC 10 ms 3572 KiB
sub2_case_02.txt AC 4 ms 3656 KiB
sub2_case_03.txt AC 25 ms 3844 KiB
sub2_case_04.txt AC 24 ms 3812 KiB
sub2_case_05.txt AC 71 ms 3860 KiB
sub2_case_06.txt AC 61 ms 4440 KiB
sub2_case_07.txt AC 266 ms 4964 KiB
sub2_case_08.txt AC 274 ms 4736 KiB
sub2_case_09.txt AC 268 ms 4896 KiB
sub2_case_10.txt AC 265 ms 4916 KiB
sub2_case_11.txt AC 271 ms 4796 KiB
sub2_case_12.txt AC 268 ms 4964 KiB
sub2_case_13.txt AC 267 ms 4856 KiB
sub2_case_14.txt AC 125 ms 4600 KiB
sub2_case_15.txt AC 125 ms 4440 KiB
sub2_case_16.txt AC 123 ms 4600 KiB
sub2_case_17.txt AC 125 ms 4476 KiB
sub2_case_18.txt AC 123 ms 4512 KiB
sub2_case_19.txt AC 73 ms 4544 KiB
sub2_case_20.txt AC 74 ms 4380 KiB
sub2_case_21.txt AC 76 ms 4508 KiB
sub2_case_22.txt AC 75 ms 4440 KiB
sub2_case_23.txt AC 75 ms 4596 KiB
sub2_case_24.txt AC 78 ms 4448 KiB
sub2_case_25.txt AC 48 ms 3644 KiB
sub2_case_26.txt AC 68 ms 3760 KiB
sub2_case_27.txt AC 67 ms 3680 KiB
sub2_case_28.txt AC 39 ms 3644 KiB