QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#770183#7860. Graph of Maximum Degree 3WilliamHuWA 4ms79516kbC++174.0kb2024-11-21 21:00:552024-11-21 21:00:55

Judging History

This is the latest submission verdict.

  • [2024-11-21 21:00:55]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 79516kb
  • [2024-11-21 21:00:55]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c != EOF and !isdigit(c))
	{
		if(c == '-')f = -1;
		c = getchar();
	}
	while(isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
int n, m, d[1000010], d1[1000010];
struct node{
	int a, b, c;
	bool operator <(const node x)const{
		if(a == x.a)return x.b == b ? (c < x.c) : (b < x.b);
		return a < x.a;
	}
};
struct nodes{
	int v, c;
};
vector<nodes>l[1000010];
set<pair<int, int> >m1;
set<node>t0;
set<node>t1;
set<pair<pair<int, int>, pair<int, int> > >s1;
int ed[1000010], ed1[1000010];
bool vis[1000010], vis1[1000010];
vector<int>chain[1000010], chain1[1000010];
vector<int>tmp;
void dfs(int u, int fa)
{
	tmp.push_back(u);
	vis[u] = 1;
	for(int i = 0;i < l[u].size();i ++)
	{
		int v = l[u][i].v, c = l[u][i].c;
		if(c != 0 or v == fa)continue;
		dfs(v, u);
	}
}
void dfs1(int u, int fa)
{
	tmp.push_back(u);
	vis1[u] = 1;
	for(int i = 0;i < l[u].size();i ++)
	{
		int v = l[u][i].v, c = l[u][i].c;
		if(c != 1 or v == fa)continue;
		dfs1(v, u);
	}
}
signed main()
{
	n = read();
	m = read();
	for(int i = 1;i <= m;i ++)
	{
		int u = read(), v = read(), c = read();
		l[u].push_back({v, c});
		l[v].push_back({u, c});
		if(c == 0)
		{
			d[u] ++;
			d[v] ++;
		}
		if(c == 1)
		{
			d1[u] ++;
			d1[v] ++;
		}
		if(u > v)swap(u, v);
		if(c == 1)m1.insert(make_pair(min(u, v), max(u, v)));
	}
	int ans = 0;
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 0;j < l[i].size();j ++)
		{
			int v = l[i][j].v, c = l[i][j].c;
			if(c == 0)
			{
				if(m1.find(make_pair(min(i, v), max(i, v))) != m1.end())ans ++;
			}
		}
		if(d[i] == 1 and !vis[i])
		{
			tmp.clear();
			dfs(i, i);
			ed[i] = tmp[tmp.size() - 1];
			chain[i] = tmp;
//			cout<<"0:"<<i<<endl;
//			for(int j = 0;j < tmp.size();j ++)cout<<tmp[j]<<' ';
//			cout<<endl;
		}
		if(d1[i] == 1 and !vis1[i])
		{
			tmp.clear();
			dfs1(i, i);
			ed1[i] = tmp[tmp.size() - 1];
			chain1[i] = tmp;
//			cout<<"1:"<<i<<endl;
//			for(int j = 0;j < tmp.size();j ++)cout<<tmp[j]<<' ';
//			cout<<endl;
		}
	}
	ans /= 2;
	//cout<<"ans:"<<ans<<endl;
	for(int i = 1;i <= n;i ++)
	{
		if(chain[i].size() < 3)continue;
		if(chain[i].size() == 3)
		{
			t0.insert({chain[i][0], chain[i][1], chain[i][2]});
		}
	}
	//cout<<"still live\n";
	for(int i = 1;i <= n;i ++)
	{
		if(chain1[i].size() < 3)continue;
		if(chain1[i].size() == 3)
		{
			t1.insert({chain1[i][0], chain1[i][1], chain1[i][2]});
		}
		if(chain1[i].size() == 4)
		{
			s1.insert(make_pair(make_pair(min(chain1[i][0], chain1[i][3]), min(chain1[i][1], chain1[i][2])), make_pair(max(chain1[i][1], chain1[i][2]), max(chain1[i][0], chain1[i][3]))));
		}
	}
	for(int i = 1;i <= n;i ++)
	{
		if(chain[i].size() <= 3)continue;
		int x = chain[i][0], y = chain[i][1], z = chain[i][2];
		if(t1.find({y, x, z}) != t1.end() or t1.find({z, x, y}) != t1.end())ans ++;
		x = chain[i][chain[i].size()-1];
		y = chain[i][chain[i].size()-2];
		z = chain[i][chain[i].size()-3];
		if(t1.find({y, x, z}) != t1.end() or t1.find({z, x, y}) != t1.end())ans ++;
	}
	for(int i = 1;i <= n;i ++)
	{
		if(chain1[i].size() <= 3)continue;
		int x = chain1[i][0], y = chain1[i][1], z = chain1[i][2];
		if(t0.find({y, x, z}) != t0.end() or t0.find({z, x, y}) != t0.end())ans ++;
		x = chain1[i][chain1[i].size()-1];
		y = chain1[i][chain1[i].size()-2];
		z = chain1[i][chain1[i].size()-3];
		if(t0.find({y, x, z}) != t0.end() or t0.find({z, x, y}) != t0.end())ans ++;
	}
	//cout<<"ans1:"<<ans<<endl;
	for(int i = 1;i <= n;i ++)
	{
		if(chain[i].size() != 4)continue;
		int x = chain[i][0], y = chain[i][1], z = chain[i][2], x1 = chain[i][3];
		//cout<<x<<y<<z<<x1<<endl;
		if(s1.find(make_pair(make_pair(min(y, z), min(x, x1)), make_pair(max(x, x1), max(y, z)))) != s1.end())ans ++;
	}
	cout<<ans+n<<'\n';
	return 0;
}
//4 6
//1 2 0
//2 3 0
//3 4 0
//1 4 1
//2 4 1
//1 3 1

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 79516kb

input:

3 4
1 2 0
1 3 1
2 3 0
2 3 1

output:

4

result:

wrong answer 1st numbers differ - expected: '5', found: '4'