Sponsors

Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals), problem: (E) Perpetual Motion Machine Solution In C/C++

#include <bits/stdc++.h>
using namespace std;

#define inf 1023456789
#define linf 1023456789123456789ll
#define pii pair<int,int>
#define pipii pair<int, pii >
#define pll pair<long long,long long>
#define vint vector<int>
#define vvint vector<vint >
#define ll long long
#define pdd pair<double, double>

//#define DEBUG
#ifdef DEBUG
#define db(x) cerr << #x << ” = ” << x << endl
#else
#define db(x)
#endif

vector<ll> value;
vector<bool> visited;
vvint sus;

vector<int> deg3, deg4;

int dfs(int node, int parent = -1)
{
if(visited[node]) return node;
visited[node] = 1;
if(sus[node].size() == 3) deg3.push_back(node);
if(sus[node].size() >= 4) deg4.push_back(node);
for(int i=0; i<sus[node].size(); i++)
{
if(sus[node][i] == parent)continue;
int ret = dfs(sus[node][i], node);
if(ret != -1)
{
if(ret == -2) return -2;
value[node] = 1;
if(ret == node) return -2;
return ret;
}
}
return -1;
}

bool mark3dfs(int node, int parent = -1)
{
if(parent != -1 && sus[node].size() >= 3)
{
value[node] = 2;
for(int i=0; i<sus[node].size(); i++) value[sus[node][i]] = 1;
return true;
}
for(int i=0; i<sus[node].size(); i++)
{
if(sus[node][i] == parent)continue;
if(mark3dfs(sus[node][i], node))
{
value[node] = 2;
return true;
}
}
return false;
}

int find_depth(int node, int parent)
{
for(int i=0; i<sus[node].size(); i++)
{
if(sus[node][i] == parent)continue;
return find_depth(sus[node][i], node) + 1;
}
return 1;
}

void color(int node, int parent, ll val, ll step)
{
val -= step;
if(val <= 0) return;
value[node] = val;
for(int i=0; i<sus[node].size(); i++)
{
if(sus[node][i] == parent)continue;
color(sus[node][i], node, val, step);
}
}

bool solve_component(int node)
{
deg3 = vint(0);
deg4 = vint(0);
if(dfs(node) == -2) return 1;
if(deg4.size() > 0)
{
int hub = deg4[0];
value[hub] = 2;
for(int i=0; i<4; i++)
{
value[sus[hub][i]] = 1;
}
return true;
}
if(deg3.size() >= 2)
{
for(int i=0; i<sus[deg3[0]].size(); i++)
{
value[sus[deg3[0]][i]] = 1;
}
mark3dfs(deg3[0]);
return true;
}
if(deg3.size() == 0)
{
return false;
}

int hub = deg3[0];
ll depth[3];
for(int i=0; i<3; i++)
{
depth[i] = min(6, 1+find_depth(sus[hub][i], hub));
}
if(depth[0] * depth[1] + depth[1] * depth[2] + depth[2] * depth[0] > depth[0]*depth[1]*depth[2])
{
return false;
}
value[hub] = 120000;
for(int i=0; i<3; i++)
{
color(sus[hub][i], hub, value[hub], (value[hub]-1)/depth[i]+1);
}
return true;
}

int main()
{
int t;
scanf(“%d”, &t);
for(int test = 0; test < t; test++)
{
int n, m;
scanf(“%d %d”, &n, &m);
sus = vector<vector<int> >(n);
for(int i=0; i<m; i++)
{
int a, b;
scanf(“%d %d”, &a, &b);
a–;
b–;
sus[a].push_back(b);
sus[b].push_back(a);
}
value = vector<ll>(n, 0);
visited = vector<bool>(n, 0);
bool solved = 0;
for(int i=0; i<n; i++)
{
if(!visited[i])
{
if(solve_component(i))
{
printf(“YES\n”);
for(int j=0; j<n; j++)
{
printf(“%d%c”, (int)(value[j]), ” \n”[j+1 == n]);
}
solved = 1;
break;
}
}
}
if(!solved)
{
printf(“NO\n”);
}
}
return 0;
}

The Independent’s “Record CO₂...

Debunking the Hype: Why the Recent CO₂ "Surge" Isn't...

China vs the World:...

America Mobilizes Global Allies Against China’s Rare Earth Export...

TiVo Stops Selling DVRs,...

The End of an Era: TiVo Exits Hardware Business...

The end of retirement?...

The End of Traditional Retirement: Securing Income After 60 The...

(no subject)

Navigating Digital Peril: Key Takeaways from the RISKS Digest...

Chicago ICE raids, National...

Chicago Schools Distribute ‘Know Your Rights’ Leaflets Amidst Heightened...

The Independent’s “Record CO₂ Surge” Story: Hype Without Context

Debunking the Hype: Why the Recent CO₂ "Surge" Isn't Just Industrial Emissions Alarmist headlines are a fixture in modern climate reporting, and a recent story...

China vs the World: US expects support from India, other allies in rare earths trade tensions

America Mobilizes Global Allies Against China’s Rare Earth Export Tensions The geopolitical chessboard is shifting once again, this time centered on critical resources. The United...

TiVo Stops Selling DVRs, Exiting the Hardware Business After 26 Years

The End of an Era: TiVo Exits Hardware Business After 26 Years, Stopping DVR Sales A quiet revolution in how Americans watched television began in...

The end of retirement? How smart career planning can secure your income and financial independence after 60

The End of Traditional Retirement: Securing Income After 60 The concept of clocking out permanently at 65 and living solely off savings is quickly becoming...

(no subject)

Navigating Digital Peril: Key Takeaways from the RISKS Digest 34.77 The digital landscape is one of constant innovation, but also persistent peril. For decades, the...

Chicago ICE raids, National Guard troops prompt new school leaflets: ‘Know your rights’

Chicago Schools Distribute ‘Know Your Rights’ Leaflets Amidst Heightened ICE Activity The atmosphere outside Nash Elementary School in Chicago recently felt different. While teachers greeted...

The Future Of Sustainable Innovation In Microplastics And Supply Chain

Revolutionizing Sustainability: How CLEANR and Worldly Axion are Reshaping Industry The push for true sustainability is no longer a niche concern—it is a mandatory requirement...

Together, Power Plants and Greenhouses Can Feed Humanity.

The Symbiotic Solution: Power Plants Fueling Global Greenhouses In the quest for sustainable practices and improved global food security, engineers are increasingly looking toward solutions...

Regional Lenders Are Merging to Answer the Challenge From Megabanks

The Consolidation Wave: Why Regional Lenders Are Merging to Fight Megabank Dominance The landscape of American banking is undergoing a rapid transformation, characterized by a...