oj.uz

답안 #1049175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1049175 2024-08-08T14:29:05 Z Ludissey Graph (BOI20_graph) C++17
0 / 100
 700 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(int a, int 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;
        if(eq(eqCOLOR[u.first],-1e9)||eqCOLOR[u.first]==(u.second)-c) dfs(u.first,(u.second)-c);
        else { no=true; return; }
    }
}

double colorCOUNT(int x){
    int sm=abs(eqCOLOR[x])*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.00000001){
                    int d=(abs(l)+abs(r))/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-0.00000001;
                    }else{
                        l=mid1+0.00000001;
                    }
                }
                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;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB answer = YES
2 Execution timed out 1020 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB answer = YES
2 Execution timed out 1020 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB answer = YES
2 Execution timed out 1020 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB answer = YES
2 Execution timed out 1020 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB answer = YES
2 Execution timed out 1020 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -