Submission #1102017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102017		razivo	Graph (BOI20_graph)	C++14	100 / 100	134 ms	11192 KiB

Graph

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Linear {
    double m,b;
    bool operator==(Linear a) const {
        return abs(m-a.m)<0.2f && abs(b-a.b)<0.2f;
    }
};
Linear Inv(Linear a) {
    return {a.m,-a.b*a.m};
}
Linear Compose(Linear a, Linear b) {
    return {a.m*b.m,b.b*a.m+a.b};
}
Linear Intersect(Linear a,Linear b) {
    return {0,-(a.b-b.b)/(a.m-b.m)};
}

Linear t1 = {-1,1};
Linear t2={-1,2};
Linear id={1,0};
vector<int> dsu;
vector<Linear> toParent;
vector<int> s;
void e() {
    cout<<"NO";
    exit(0);
}
pair<int,Linear> find(int a) {
    if(dsu[a]==a) return {a,id};
    auto [b,l] = find(dsu[a]);
    return {b,Compose(l,toParent[a])};
}
void un(int a,int b,Linear type) {
    auto [ap,la] = find(a);
    auto [bp,lb] = find(b);
    if(ap==bp) {
        if(Compose(type,Compose(Inv(la),toParent[ap]))==Compose(Inv(lb),toParent[bp])) {
            return;
        }else {
            if(!(toParent[ap]==id)) e();
            if(abs(la.m-lb.m)>0.2f) e();
            toParent[ap] = Intersect(Compose(type,Inv(la)),Inv(lb));
        }
    }else {
        if(s[bp]<s[ap]) {
            swap(ap,bp);
            swap(la,lb);
        }
        Linear atob = Compose(Compose(lb,type),Inv(la));
        if(toParent[ap]==id) {
            toParent[ap]=atob;
        }else {
            if(toParent[bp]==id) {
                toParent[bp]=Compose(atob,toParent[ap]);
                toParent[ap]=atob;
            }else {
                if(Compose(atob,toParent[ap])==toParent[bp]) {
                    toParent[ap]=atob;
                }else {
                    e();
                }
            }
        }
        dsu[ap]=bp;
        s[bp]+=s[ap];
    }
}
void Solve(vector<pair<int,Linear>> &g,vector<double> &res) {
    sort(g.begin(), g.end(),[](pair<int,Linear> a,pair<int,Linear> b) {
        return b.second.b*b.second.m>a.second.b*a.second.m;
    });
    double t = -g[g.size()/2].second.b*g[g.size()/2].second.m;
    for(auto [a,l]:g) {
        res[a] = Compose(l,{0,t}).b;
    }
}
int main() {
    int n,m;cin>>n>>m;
    for (int i = 0; i < n; ++i) {
        dsu.push_back(i);
        toParent.push_back(id);
        s.push_back(1);
    }
    for (int i = 0; i < m; ++i) {
        int x,y,t; cin>>x>>y>>t; x--; y--;
        if(t==1) {
            un(x,y,t1);
        }else {
            un(x,y,t2);
        }
    }
    vector<vector<pair<int,Linear>>> g(n);
    vector<bool> type(n,true);
    for (int i = 0; i < n; ++i) {
        auto [a,l]=find(i);
        l= Compose(Inv(l),toParent[a]);
        if(abs(l.m)<0.2f) type[a]=false;
        g[a].push_back({i,l});
    }
    vector<double> res(n);
    for (int i = 0; i < n; ++i) {
        if(g[i].size()==0) continue;
        if(type[i]) {
            Solve(g[i],res);
        }else {
            for(auto u : g[i]) {
                res[u.first]=u.second.b;
            }
        }
    }
    cout<<"YES"<<endl;
    for (int i = 0; i < n; ++i) {
        cout<<res[i]<<" ";
    }
}

Compilation message (stderr)

Graph.cpp: In function 'std::pair<int, Linear> find(int)':
Graph.cpp:33:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     auto [b,l] = find(dsu[a]);
      |          ^
Graph.cpp: In function 'void un(int, int, Linear)':
Graph.cpp:37:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     auto [ap,la] = find(a);
      |          ^
Graph.cpp:38:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     auto [bp,lb] = find(b);
      |          ^
Graph.cpp: In function 'void Solve(std::vector<std::pair<int, Linear> >&, std::vector<double>&)':
Graph.cpp:76:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for(auto [a,l]:g) {
      |              ^
Graph.cpp: In function 'int main()':
Graph.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |         auto [a,l]=find(i);
      |              ^

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42