| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1049106 |
2024-08-08T13:26:42 Z |
Ludissey |
Graph (BOI20_graph) |
C++17 |
|
1 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<int> eqCOLOR;
bool no=false;
int getParent(int a){
return (a==parent[a]) ? a : parent[a]=getParent(parent[a]);
}
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, int c){
eqCOLOR[x]=c;
visited[x]=true;
for (auto u : neigh[x])
{
if(visited[u.first]) continue;
if(eqCOLOR[u.first]==-1||eqCOLOR[u.first]==(u.second*2)-c) dfs(u.first,(u.second*2)-c);
else { no=true; return; }
}
}
int colorCOUNT(int x){
int sm=eqCOLOR[x];
visited[x]=false;
eqCOLOR[x]=-1;
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,-1);
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(eqCOLOR[getParent(i)]==2){
cout << "NO\n";
return 0;
}
eqCOLOR[getParent(i)]=1;
}
}
for (int j = 0; j < sz(neigh2[i]); j++) {
if(getParent(i)==getParent(neigh2[i][j])) {
if(eqCOLOR[getParent(i)]==1) {
cout << "NO\n";
return 0;
}
eqCOLOR[getParent(i)]=2;
}
}
}
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{
int c1=0,c2=0;
for (auto u : neigh[j])
{
dfs(u.first,0);
c2=colorCOUNT(j);
break;
}
if(c1<c2){
dfs(i,0);
}else{
for (auto u : neigh[j])
{
dfs(u.first,0);
break;
}
}
}
}
}
for (int i = 0; i < M; i++)
{
if(eqCOLOR[getParent(ed[i].first.first)]+eqCOLOR[getParent(ed[i].first.second)]!=ed[i].second*2) no=true;
}
if(no){
cout << "NO\n";
}else{
cout << "YES\n";
for (int i = 0; i < N; i++)
{
cout << (double)(eqCOLOR[getParent(i)])/2<<" ";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
348 KB |
answer = YES |
| 3 |
Correct |
0 ms |
348 KB |
answer = YES |
| 4 |
Correct |
0 ms |
348 KB |
answer = NO |
| 5 |
Correct |
0 ms |
348 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
348 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
348 KB |
answer = YES |
| 3 |
Correct |
0 ms |
348 KB |
answer = YES |
| 4 |
Correct |
0 ms |
348 KB |
answer = NO |
| 5 |
Correct |
0 ms |
348 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
348 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
348 KB |
answer = YES |
| 3 |
Correct |
0 ms |
348 KB |
answer = YES |
| 4 |
Correct |
0 ms |
348 KB |
answer = NO |
| 5 |
Correct |
0 ms |
348 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
348 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
348 KB |
answer = YES |
| 3 |
Correct |
0 ms |
348 KB |
answer = YES |
| 4 |
Correct |
0 ms |
348 KB |
answer = NO |
| 5 |
Correct |
0 ms |
348 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
348 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
348 KB |
answer = YES |
| 3 |
Correct |
0 ms |
348 KB |
answer = YES |
| 4 |
Correct |
0 ms |
348 KB |
answer = NO |
| 5 |
Correct |
0 ms |
348 KB |
answer = YES |
| 6 |
Incorrect |
1 ms |
348 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
