QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#294301	#4829. Mark on a Graph	ucup-team987^#	AC ✓	2ms	4268kb	C++20	3.2kb	2023-12-30 11:37:08	2023-12-30 11:37:08

Judging History

你现在查看的是最新测评结果

[2023-12-30 11:37:08]
评测

测评结果：AC
用时：2ms
内存：4268kb

查看

[2023-12-30 11:37:08]
提交

answer

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<cassert>
#include<random>
using namespace std;
const int N=1000;
mt19937 rng;
int U[5050],V[5050];
int deg[N];
vector<pair<int,int> >G[N];
bool vis[N];
vector<int>mark[5050];
unsigned long long A[N];
long long countK4(vector<pair<int,int> >E)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int M=E.size();
	for(int i=0;i<N;i++)
	{
		G[i].clear();
		vis[i]=false;
		deg[i]=0;
	}
	for(int i=0;i<M;i++)
	{
		U[i]=E[i].first,V[i]=E[i].second;
		deg[U[i]]++;
		deg[V[i]]++;
	}
	for(int i=0;i<M;i++)
	{
		if(deg[U[i]]>deg[V[i]])swap(U[i],V[i]);
		G[U[i]].push_back(make_pair(V[i],i));
	}
	vector<int>tmp;tmp.reserve(N);
	for(int u=0;u<N;u++)
	{
		for(pair<int,int>e:G[u])vis[e.first]=true;
		tmp.clear();
		for(pair<int,int>e:G[u])
		{
			int v=e.first;
			tmp.clear();
			for(pair<int,int>f:G[v])if(vis[f.first])tmp.push_back(f.first);
			mark[e.second].resize(tmp.size());
			for(int i=0;i<tmp.size();i++)mark[e.second][i]=tmp[i];
		}
		for(pair<int,int>e:G[u])vis[e.first]=false;
	}
	long long ans=0;
	for(int i=0;i<M;i+=64)
	{
		for(int j=0;j<N;j++)A[j]=0;
		int c=min(i+64,M)-i;
		for(int k=0;k<c;k++)for(int v:mark[i+k])A[v]|=1uLL<<k;
		for(int j=0;j<M;j++)ans+=__builtin_popcountll(A[U[j]]&A[V[j]]);
	}
	return ans;
}
vector<pair<int,int> >gen_G()
{
	set<pair<int,int> >E;
	int M=2000+rng()%(5000-2000+1);
	while(E.size()<M)
	{
		int u=rng()%N,v=rng()%N;
		if(u>v)swap(u,v);
		if(u==v||E.find(make_pair(u,v))!=E.end())continue;
		E.insert(make_pair(u,v));
	}
	return vector<pair<int,int> >(E.begin(),E.end());
}
vector<pair<int,int> >read_G()
{
	int n,m;
	cin>>n>>m;
	assert(n==N);
	vector<pair<int,int> >E(m);
	for(int i=0;i<m;i++)
	{
		int u,v;cin>>u>>v;u--,v--;
		if(u>v)swap(u,v);
		E[i]=make_pair(u,v);
	}
	return E;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//while(true)
	{
		//vector<pair<int,int> >E=gen_G();
		vector<pair<int,int> >E=read_G();
		int preK4=countK4(E);
		if(preK4>=2)
		{
			cout<<"ok"<<endl;
			return 0;
		}
		assert(preK4<=1);
		vector<int>deg(N);
		for(auto[u,v]:E)deg[u]++,deg[v]++;
		int mxu=0;
		for(int i=1;i<N;i++)if(deg[mxu]<deg[i])mxu=i;
		assert(deg[mxu]>=4);
		vector<int>V;
		for(auto[u,v]:E)
		{
			if(u==mxu)V.push_back(v);
			else if(v==mxu)V.push_back(u);
		}
		assert(V.size()==deg[mxu]);
		V.resize(4);
		sort(V.begin(),V.end());
		V.erase(unique(V.begin(),V.end()),V.end());
		assert(V.size()==4);
		vector<pair<int,int> >need;
		need.push_back(make_pair(V[0],V[1]));
		need.push_back(make_pair(V[0],V[2]));
		need.push_back(make_pair(V[1],V[2]));
		need.push_back(make_pair(V[1],V[3]));
		need.push_back(make_pair(V[2],V[3]));
		sort(E.begin(),E.end());
		vector<pair<int,int> >ans;
		for(pair<int,int>e:need)
		{
			auto it=lower_bound(E.begin(),E.end(),e);
			if(it!=E.end()&&*it==e)continue;
			ans.push_back(e);
		}
		for(pair<int,int>e:ans)E.push_back(e);
		int nowK4=countK4(E);
		assert(nowK4>=2);
		cout<<"mark\n";
		cout<<ans.size()<<endl;
		for(auto[u,v]:ans)cout<<u+1<<" "<<v+1<<endl;
		//cout<<preK4<<" "<<nowK4<<endl;
	}
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 4192kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 1ms

memory: 3856kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 1ms

memory: 4040kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 1ms

memory: 3876kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 1ms

memory: 4128kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 1ms

memory: 3900kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 1ms

memory: 4088kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 1ms

memory: 3968kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 2ms

memory: 3948kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 2ms

memory: 3976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 1ms

memory: 4056kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 2ms

memory: 4192kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 1ms

memory: 4008kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 1ms

memory: 4156kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 1ms

memory: 4088kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 1ms

memory: 3952kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 1ms

memory: 3904kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 2ms

memory: 4208kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 2ms

memory: 3888kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 2ms

memory: 3976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 1ms

memory: 4096kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 1ms

memory: 3896kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 1ms

memory: 4116kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 1ms

memory: 4036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 1ms

memory: 4104kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 2ms

memory: 4104kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 1ms

memory: 3888kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 2ms

memory: 3988kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 1ms

memory: 3928kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 2ms

memory: 3944kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 1ms

memory: 3900kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 2ms

memory: 4220kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 2ms

memory: 4208kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 1ms

memory: 3832kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 1ms

memory: 3896kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 1ms

memory: 4092kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 1ms

memory: 4076kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 1ms

memory: 3828kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 1ms

memory: 3856kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 1ms

memory: 3856kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 1ms

memory: 3792kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 1ms

memory: 4056kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 1ms

memory: 3856kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 1ms

memory: 4020kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 1ms

memory: 3856kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 1ms

memory: 4036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 1ms

memory: 4056kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 1ms

memory: 4052kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 2ms

memory: 3984kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 2ms

memory: 4048kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 2ms

memory: 4168kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 2ms

memory: 3984kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 2ms

memory: 4040kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 2ms

memory: 4244kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 2ms

memory: 4216kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 1ms

memory: 4268kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 2ms

memory: 4048kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 2ms

memory: 4008kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 2ms

memory: 4212kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 2ms

memory: 4036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 2ms

memory: 3992kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 2ms

memory: 4052kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 2ms

memory: 3980kb

input:

output:

input:

output:

ok

result:

ok all right