oj.uz

Submission #1102017

# Submission time Handle Problem Language Result Execution time Memory
1102017 2024-10-17T09:55:54 Z razivo Graph (BOI20_graph) C++14
100 / 100
 134 ms 11192 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 0 ms 336 KB answer = NO
5 Correct 1 ms 504 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 0 ms 336 KB answer = YES
8 Correct 0 ms 336 KB answer = YES
9 Correct 1 ms 336 KB answer = NO
10 Correct 1 ms 336 KB answer = YES
11 Correct 0 ms 336 KB answer = YES
12 Correct 0 ms 336 KB answer = NO
13 Correct 1 ms 336 KB answer = YES
14 Correct 1 ms 336 KB answer = YES
15 Correct 1 ms 336 KB answer = YES
16 Correct 1 ms 336 KB answer = YES
17 Correct 1 ms 336 KB answer = YES
18 Correct 1 ms 336 KB answer = YES
19 Correct 1 ms 412 KB answer = YES
20 Correct 1 ms 504 KB answer = YES
21 Correct 1 ms 336 KB answer = YES
22 Correct 1 ms 336 KB answer = NO
23 Correct 0 ms 336 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 0 ms 336 KB answer = NO
5 Correct 1 ms 504 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 0 ms 336 KB answer = YES
8 Correct 0 ms 336 KB answer = YES
9 Correct 1 ms 336 KB answer = NO
10 Correct 1 ms 336 KB answer = YES
11 Correct 0 ms 336 KB answer = YES
12 Correct 0 ms 336 KB answer = NO
13 Correct 1 ms 336 KB answer = YES
14 Correct 1 ms 336 KB answer = YES
15 Correct 1 ms 336 KB answer = YES
16 Correct 1 ms 336 KB answer = YES
17 Correct 1 ms 336 KB answer = YES
18 Correct 1 ms 336 KB answer = YES
19 Correct 1 ms 412 KB answer = YES
20 Correct 1 ms 504 KB answer = YES
21 Correct 1 ms 336 KB answer = YES
22 Correct 1 ms 336 KB answer = NO
23 Correct 0 ms 336 KB answer = NO
24 Correct 1 ms 336 KB answer = YES
25 Correct 1 ms 336 KB answer = YES
26 Correct 1 ms 336 KB answer = YES
27 Correct 1 ms 336 KB answer = YES
28 Correct 1 ms 348 KB answer = YES
29 Correct 1 ms 508 KB answer = YES
30 Correct 1 ms 336 KB answer = NO
31 Correct 1 ms 336 KB answer = YES
32 Correct 1 ms 336 KB answer = YES
33 Correct 1 ms 336 KB answer = YES
34 Correct 1 ms 336 KB answer = YES
35 Correct 1 ms 336 KB answer = YES
36 Correct 1 ms 336 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 0 ms 336 KB answer = NO
5 Correct 1 ms 504 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 0 ms 336 KB answer = YES
8 Correct 0 ms 336 KB answer = YES
9 Correct 1 ms 336 KB answer = NO
10 Correct 1 ms 336 KB answer = YES
11 Correct 0 ms 336 KB answer = YES
12 Correct 0 ms 336 KB answer = NO
13 Correct 1 ms 336 KB answer = YES
14 Correct 1 ms 336 KB answer = YES
15 Correct 1 ms 336 KB answer = YES
16 Correct 1 ms 336 KB answer = YES
17 Correct 1 ms 336 KB answer = YES
18 Correct 1 ms 336 KB answer = YES
19 Correct 1 ms 412 KB answer = YES
20 Correct 1 ms 504 KB answer = YES
21 Correct 1 ms 336 KB answer = YES
22 Correct 1 ms 336 KB answer = NO
23 Correct 0 ms 336 KB answer = NO
24 Correct 1 ms 336 KB answer = YES
25 Correct 1 ms 336 KB answer = YES
26 Correct 1 ms 336 KB answer = YES
27 Correct 1 ms 336 KB answer = YES
28 Correct 1 ms 348 KB answer = YES
29 Correct 1 ms 508 KB answer = YES
30 Correct 1 ms 336 KB answer = NO
31 Correct 1 ms 336 KB answer = YES
32 Correct 1 ms 336 KB answer = YES
33 Correct 1 ms 336 KB answer = YES
34 Correct 1 ms 336 KB answer = YES
35 Correct 1 ms 336 KB answer = YES
36 Correct 1 ms 336 KB answer = YES
37 Correct 1 ms 504 KB answer = YES
38 Correct 1 ms 336 KB answer = YES
39 Correct 1 ms 336 KB answer = YES
40 Correct 1 ms 336 KB answer = YES
41 Correct 1 ms 336 KB answer = NO
42 Correct 1 ms 336 KB answer = YES
43 Correct 1 ms 336 KB answer = YES
44 Correct 1 ms 336 KB answer = YES
45 Correct 1 ms 336 KB answer = YES
46 Correct 1 ms 336 KB answer = YES
47 Correct 1 ms 336 KB answer = YES
48 Correct 2 ms 336 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 0 ms 336 KB answer = NO
5 Correct 1 ms 504 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 0 ms 336 KB answer = YES
8 Correct 0 ms 336 KB answer = YES
9 Correct 1 ms 336 KB answer = NO
10 Correct 1 ms 336 KB answer = YES
11 Correct 0 ms 336 KB answer = YES
12 Correct 0 ms 336 KB answer = NO
13 Correct 1 ms 336 KB answer = YES
14 Correct 1 ms 336 KB answer = YES
15 Correct 1 ms 336 KB answer = YES
16 Correct 1 ms 336 KB answer = YES
17 Correct 1 ms 336 KB answer = YES
18 Correct 1 ms 336 KB answer = YES
19 Correct 1 ms 412 KB answer = YES
20 Correct 1 ms 504 KB answer = YES
21 Correct 1 ms 336 KB answer = YES
22 Correct 1 ms 336 KB answer = NO
23 Correct 0 ms 336 KB answer = NO
24 Correct 1 ms 336 KB answer = YES
25 Correct 1 ms 336 KB answer = YES
26 Correct 1 ms 336 KB answer = YES
27 Correct 1 ms 336 KB answer = YES
28 Correct 1 ms 348 KB answer = YES
29 Correct 1 ms 508 KB answer = YES
30 Correct 1 ms 336 KB answer = NO
31 Correct 1 ms 336 KB answer = YES
32 Correct 1 ms 336 KB answer = YES
33 Correct 1 ms 336 KB answer = YES
34 Correct 1 ms 336 KB answer = YES
35 Correct 1 ms 336 KB answer = YES
36 Correct 1 ms 336 KB answer = YES
37 Correct 1 ms 504 KB answer = YES
38 Correct 1 ms 336 KB answer = YES
39 Correct 1 ms 336 KB answer = YES
40 Correct 1 ms 336 KB answer = YES
41 Correct 1 ms 336 KB answer = NO
42 Correct 1 ms 336 KB answer = YES
43 Correct 1 ms 336 KB answer = YES
44 Correct 1 ms 336 KB answer = YES
45 Correct 1 ms 336 KB answer = YES
46 Correct 1 ms 336 KB answer = YES
47 Correct 1 ms 336 KB answer = YES
48 Correct 2 ms 336 KB answer = YES
49 Correct 8 ms 1468 KB answer = YES
50 Correct 9 ms 1532 KB answer = YES
51 Correct 9 ms 1468 KB answer = YES
52 Correct 5 ms 848 KB answer = NO
53 Correct 3 ms 336 KB answer = YES
54 Correct 2 ms 592 KB answer = YES
55 Correct 5 ms 848 KB answer = YES
56 Correct 8 ms 1468 KB answer = YES
57 Correct 8 ms 1228 KB answer = YES
58 Correct 7 ms 1228 KB answer = YES
59 Correct 8 ms 1240 KB answer = YES
60 Correct 9 ms 1228 KB answer = YES
61 Correct 5 ms 848 KB answer = YES
62 Correct 3 ms 616 KB answer = NO
63 Correct 98 ms 1104 KB answer = YES
64 Correct 83 ms 592 KB answer = NO
65 Correct 84 ms 1096 KB answer = YES
66 Correct 2 ms 592 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB answer = YES
2 Correct 1 ms 336 KB answer = YES
3 Correct 1 ms 336 KB answer = YES
4 Correct 0 ms 336 KB answer = NO
5 Correct 1 ms 504 KB answer = YES
6 Correct 1 ms 336 KB answer = YES
7 Correct 0 ms 336 KB answer = YES
8 Correct 0 ms 336 KB answer = YES
9 Correct 1 ms 336 KB answer = NO
10 Correct 1 ms 336 KB answer = YES
11 Correct 0 ms 336 KB answer = YES
12 Correct 0 ms 336 KB answer = NO
13 Correct 1 ms 336 KB answer = YES
14 Correct 1 ms 336 KB answer = YES
15 Correct 1 ms 336 KB answer = YES
16 Correct 1 ms 336 KB answer = YES
17 Correct 1 ms 336 KB answer = YES
18 Correct 1 ms 336 KB answer = YES
19 Correct 1 ms 412 KB answer = YES
20 Correct 1 ms 504 KB answer = YES
21 Correct 1 ms 336 KB answer = YES
22 Correct 1 ms 336 KB answer = NO
23 Correct 0 ms 336 KB answer = NO
24 Correct 1 ms 336 KB answer = YES
25 Correct 1 ms 336 KB answer = YES
26 Correct 1 ms 336 KB answer = YES
27 Correct 1 ms 336 KB answer = YES
28 Correct 1 ms 348 KB answer = YES
29 Correct 1 ms 508 KB answer = YES
30 Correct 1 ms 336 KB answer = NO
31 Correct 1 ms 336 KB answer = YES
32 Correct 1 ms 336 KB answer = YES
33 Correct 1 ms 336 KB answer = YES
34 Correct 1 ms 336 KB answer = YES
35 Correct 1 ms 336 KB answer = YES
36 Correct 1 ms 336 KB answer = YES
37 Correct 1 ms 504 KB answer = YES
38 Correct 1 ms 336 KB answer = YES
39 Correct 1 ms 336 KB answer = YES
40 Correct 1 ms 336 KB answer = YES
41 Correct 1 ms 336 KB answer = NO
42 Correct 1 ms 336 KB answer = YES
43 Correct 1 ms 336 KB answer = YES
44 Correct 1 ms 336 KB answer = YES
45 Correct 1 ms 336 KB answer = YES
46 Correct 1 ms 336 KB answer = YES
47 Correct 1 ms 336 KB answer = YES
48 Correct 2 ms 336 KB answer = YES
49 Correct 8 ms 1468 KB answer = YES
50 Correct 9 ms 1532 KB answer = YES
51 Correct 9 ms 1468 KB answer = YES
52 Correct 5 ms 848 KB answer = NO
53 Correct 3 ms 336 KB answer = YES
54 Correct 2 ms 592 KB answer = YES
55 Correct 5 ms 848 KB answer = YES
56 Correct 8 ms 1468 KB answer = YES
57 Correct 8 ms 1228 KB answer = YES
58 Correct 7 ms 1228 KB answer = YES
59 Correct 8 ms 1240 KB answer = YES
60 Correct 9 ms 1228 KB answer = YES
61 Correct 5 ms 848 KB answer = YES
62 Correct 3 ms 616 KB answer = NO
63 Correct 98 ms 1104 KB answer = YES
64 Correct 83 ms 592 KB answer = NO
65 Correct 84 ms 1096 KB answer = YES
66 Correct 2 ms 592 KB answer = YES
67 Correct 77 ms 10936 KB answer = YES
68 Correct 73 ms 10936 KB answer = YES
69 Correct 73 ms 10940 KB answer = YES
70 Correct 115 ms 10896 KB answer = YES
71 Correct 80 ms 10936 KB answer = YES
72 Correct 77 ms 10940 KB answer = YES
73 Correct 74 ms 10936 KB answer = YES
74 Correct 54 ms 6072 KB answer = YES
75 Correct 3 ms 2412 KB answer = NO
76 Correct 10 ms 1528 KB answer = YES
77 Correct 21 ms 2760 KB answer = YES
78 Correct 35 ms 4804 KB answer = YES
79 Correct 68 ms 10372 KB answer = YES
80 Correct 58 ms 6072 KB answer = YES
81 Correct 43 ms 4548 KB answer = NO
82 Correct 81 ms 10884 KB answer = YES
83 Correct 84 ms 10936 KB answer = YES
84 Correct 90 ms 10888 KB answer = YES
85 Correct 77 ms 10904 KB answer = YES
86 Correct 74 ms 10944 KB answer = YES
87 Correct 39 ms 4548 KB answer = NO
88 Correct 86 ms 10124 KB answer = YES
89 Correct 84 ms 11192 KB answer = YES
90 Correct 84 ms 11192 KB answer = YES
91 Correct 88 ms 11192 KB answer = YES
92 Correct 43 ms 5060 KB answer = YES
93 Correct 40 ms 5052 KB answer = YES
94 Correct 48 ms 4548 KB answer = NO
95 Correct 45 ms 4548 KB answer = NO
96 Correct 134 ms 10944 KB answer = YES
97 Correct 47 ms 4548 KB answer = NO