QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#770183 | #7860. Graph of Maximum Degree 3 | WilliamHu | WA | 4ms | 79516kb | C++17 | 4.0kb | 2024-11-21 21:00:55 | 2024-11-21 21:00:55 |
Judging History
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'