| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1049189 |
2024-08-08T14:40:46 Z |
Ludissey |
Graph (BOI20_graph) |
C++17 |
|
0 ms |
348 KB |
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<vector<int>> neigh1;
vector<vector<int>> neigh2;
vector<int> sz;
vector<int> visited;
vector<int> parent;
vector<double> eqCOLOR;
bool no=false;
int getParent(int a){
return (a==parent[a]) ? a : parent[a]=getParent(parent[a]);
}
bool eq(double a, double b){
if(abs(a-b)>0.00000001) return false;
return true;
}
void unite(int a, int b){
a=getParent(a); b=getParent(b);
if(a==b) return;
if(sz[a]<sz[b]) swap(a,b);
sz[a]+=sz[b];
parent[b]=a;
}
vector<set<pair<int,int>>> neigh;
void dfs(int x, double c){
eqCOLOR[x]=c;
visited[x]=true;
for (auto u : neigh[x])
{
if(visited[u.first]) continue;
double diff=(double)(u.second)-c;
if(eq(eqCOLOR[u.first],-1e9)||eq(eqCOLOR[u.first],diff)) dfs(u.first,diff);
else { no=true; return; }
}
}
double colorCOUNT(int x){
double sm=abs(eqCOLOR[x])*(double)sz[x];
visited[x]=false;
eqCOLOR[x]=-1e9;
for (auto u : neigh[x])
{
if(!visited[u.first]) continue;
sm+=colorCOUNT(u.first);
}
return sm;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int N,M; cin >> N >> M;
neigh1.resize(N);
sz.resize(N,1);
parent.resize(N,1);
eqCOLOR.resize(N,-1e9);
neigh2.resize(N);
vector<pair<pair<int,int>,int>> ed(M);
for (int i = 0; i < N; i++) parent[i]=i;
for (int i = 0; i < M; i++)
{
int a,b,c; cin >> a >> b >> c;
a--;
b--;
if(c==1){
neigh1[a].push_back(b);
neigh1[b].push_back(a);
}else{
neigh2[a].push_back(b);
neigh2[b].push_back(a);
}
ed[i]={{a,b},c};
}
for (int i = 0; i < N; i++){
for (int j = 1; j < sz(neigh1[i]); j++) unite(neigh1[i][j-1],neigh1[i][j]);
for (int j = 1; j < sz(neigh2[i]); j++) unite(neigh2[i][j-1],neigh2[i][j]);
}
unordered_map<int,int> mp;
for (int i = 0; i < N; i++){
for (int j = 0; j < sz(neigh1[i]); j++) mp[getParent(neigh1[i][j])]=i+1;
for (int j = 0; j < sz(neigh2[i]); j++) {
if(mp[getParent(neigh2[i][j])]==i+1) {
cout << "NO\n";
return 0;
}
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < sz(neigh1[i]); j++) {
if(getParent(i)==getParent(neigh1[i][j])) {
if(eq(eqCOLOR[getParent(i)],1)){
cout << "NO\n";
return 0;
}
eqCOLOR[getParent(i)]=0.5;
}
}
for (int j = 0; j < sz(neigh2[i]); j++) {
if(getParent(i)==getParent(neigh2[i][j])) {
if(eq(eqCOLOR[getParent(i)],0.5)) {
cout << "NO\n";
return 0;
}
eqCOLOR[getParent(i)]=1;
}
}
}
neigh.resize(N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < sz(neigh1[i]); j++) {
if(getParent(i)!=getParent(neigh1[i][j])) neigh[getParent(i)].insert({getParent(neigh1[i][j]),1});
}
for (int j = 0; j < sz(neigh2[i]); j++) {
if(getParent(i)!=getParent(neigh2[i][j])) neigh[getParent(i)].insert({getParent(neigh2[i][j]),2});
}
}
visited.resize(N,false);
for (int i = 0; i < N; i++){
int j=getParent(i);
if(!visited[j]&&eqCOLOR[j]>0) dfs(j,eqCOLOR[j]);
}
for (int i = 0; i < N; i++){
int j=getParent(i);
if(!visited[j]){
if(sz(neigh[j])==0) dfs(j,0); // securite
else{
double l=-2, r=2;
while(r-l>0.0000001){
double d=(abs(l)+abs(r))/(double)4;
double mid1=l+d;
double mid2=r-d;
dfs(j,mid1);
double c1=colorCOUNT(j);
dfs(j,mid2);
double c2=colorCOUNT(j);
if(c1<c2){
r=mid2;
}else{
l=mid1;
}
}
dfs(j,l);
}
}
}
for (int i = 0; i < M; i++)
{
if(!eq(eqCOLOR[getParent(ed[i].first.first)]+eqCOLOR[getParent(ed[i].first.second)],(double)ed[i].second)) no=true;
}
if(no){
cout << "NO\n";
}else{
cout << "YES\n";
for (int i = 0; i < N; i++)
{
cout << fixed << setprecision(6) << (double)(eqCOLOR[getParent(i)])<<" ";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
