oj.uz

Submission #906778

# Submission time Handle Problem Language Result Execution time Memory
906778 2024-01-15T01:22:55 Z Darren0724 Graph (BOI20_graph) C++17
100 / 100
 139 ms 36564 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int INF=1e18;
int n,m;
vector<pair<int,int>> adj[N];
vector<int> a(N),b(N),vis(N),ans(N),rec; //ax+b
int x=INF;
void dfs(int k){
    vis[k]=1;
    rec.push_back(k);
    for(auto [e,f]:adj[k]){
        if(!vis[e]){
            a[e]=-a[k];
            b[e]=f-b[k];
            dfs(e);
        }
        else{
            int a1=-a[k];
            int b1=f-b[k];
            if((a1==a[e]&&b1!=b[e])){
                cout<<"NO"<<endl;
                exit(0);
            }
            if(a1!=a[e]){
                int x1=(b1-b[e])/(a[e]-a1);
                if(x==INF){
                    x=x1;
                }
                else if(x!=x1){
                    cout<<"NO"<<endl;
                    exit(0);
                }
            }
        }
    }

}
int32_t main() {
    LCBorz;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].push_back({b,c<<1});
        adj[b].push_back({a,c<<1});
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            x=INF;
            a[i]=1;
            rec.clear();
            dfs(i);
            if(x==INF){
                vector<int> t;
                for(int j:rec){
                    t.push_back(-a[j]*b[j]);
                }
                sort(all(t));
                int sz=rec.size();
                x=t[sz/2];
            }
            for(int j:rec){
                ans[j]=a[j]*x+b[j];
            }
            
        }
    }
    cout<<"YES"<<endl;
    cout<<fixed<<setprecision(9);
    for(int i=1;i<=n;i++){
        cout<<(double)ans[i]/2<<' ';
    }
    cout<<endl;

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 4 ms 11408 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11352 KB answer = NO
5 Correct 5 ms 11352 KB answer = YES
6 Correct 4 ms 11384 KB answer = YES
7 Correct 4 ms 11356 KB answer = YES
8 Correct 5 ms 11356 KB answer = YES
9 Correct 4 ms 11352 KB answer = NO
10 Correct 4 ms 11356 KB answer = YES
11 Correct 4 ms 11356 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 4 ms 11356 KB answer = YES
14 Correct 4 ms 11240 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 4 ms 11356 KB answer = YES
17 Correct 4 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 4 ms 11352 KB answer = YES
20 Correct 5 ms 11356 KB answer = YES
21 Correct 4 ms 11356 KB answer = YES
22 Correct 5 ms 11356 KB answer = NO
23 Correct 4 ms 11352 KB answer = NO
24 Correct 5 ms 11356 KB answer = YES
25 Correct 4 ms 11356 KB answer = YES
26 Correct 5 ms 11436 KB answer = YES
27 Correct 4 ms 11352 KB answer = YES
28 Correct 5 ms 11356 KB answer = YES
29 Correct 5 ms 11352 KB answer = YES
30 Correct 4 ms 11356 KB answer = NO
31 Correct 5 ms 11280 KB answer = YES
32 Correct 5 ms 11356 KB answer = YES
33 Correct 5 ms 11360 KB answer = YES
34 Correct 5 ms 11368 KB answer = YES
35 Correct 6 ms 11368 KB answer = YES
36 Correct 5 ms 11352 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 4 ms 11408 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11352 KB answer = NO
5 Correct 5 ms 11352 KB answer = YES
6 Correct 4 ms 11384 KB answer = YES
7 Correct 4 ms 11356 KB answer = YES
8 Correct 5 ms 11356 KB answer = YES
9 Correct 4 ms 11352 KB answer = NO
10 Correct 4 ms 11356 KB answer = YES
11 Correct 4 ms 11356 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 4 ms 11356 KB answer = YES
14 Correct 4 ms 11240 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 4 ms 11356 KB answer = YES
17 Correct 4 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 4 ms 11352 KB answer = YES
20 Correct 5 ms 11356 KB answer = YES
21 Correct 4 ms 11356 KB answer = YES
22 Correct 5 ms 11356 KB answer = NO
23 Correct 4 ms 11352 KB answer = NO
24 Correct 5 ms 11356 KB answer = YES
25 Correct 4 ms 11356 KB answer = YES
26 Correct 5 ms 11436 KB answer = YES
27 Correct 4 ms 11352 KB answer = YES
28 Correct 5 ms 11356 KB answer = YES
29 Correct 5 ms 11352 KB answer = YES
30 Correct 4 ms 11356 KB answer = NO
31 Correct 5 ms 11280 KB answer = YES
32 Correct 5 ms 11356 KB answer = YES
33 Correct 5 ms 11360 KB answer = YES
34 Correct 5 ms 11368 KB answer = YES
35 Correct 6 ms 11368 KB answer = YES
36 Correct 5 ms 11352 KB answer = YES
37 Correct 5 ms 11356 KB answer = YES
38 Correct 5 ms 11452 KB answer = YES
39 Correct 5 ms 11356 KB answer = YES
40 Correct 6 ms 11352 KB answer = YES
41 Correct 5 ms 11356 KB answer = NO
42 Correct 5 ms 11356 KB answer = YES
43 Correct 5 ms 11448 KB answer = YES
44 Correct 6 ms 11356 KB answer = YES
45 Correct 5 ms 11356 KB answer = YES
46 Correct 5 ms 11356 KB answer = YES
47 Correct 5 ms 11352 KB answer = YES
48 Correct 5 ms 11356 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 4 ms 11408 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11352 KB answer = NO
5 Correct 5 ms 11352 KB answer = YES
6 Correct 4 ms 11384 KB answer = YES
7 Correct 4 ms 11356 KB answer = YES
8 Correct 5 ms 11356 KB answer = YES
9 Correct 4 ms 11352 KB answer = NO
10 Correct 4 ms 11356 KB answer = YES
11 Correct 4 ms 11356 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 4 ms 11356 KB answer = YES
14 Correct 4 ms 11240 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 4 ms 11356 KB answer = YES
17 Correct 4 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 4 ms 11352 KB answer = YES
20 Correct 5 ms 11356 KB answer = YES
21 Correct 4 ms 11356 KB answer = YES
22 Correct 5 ms 11356 KB answer = NO
23 Correct 4 ms 11352 KB answer = NO
24 Correct 5 ms 11356 KB answer = YES
25 Correct 4 ms 11356 KB answer = YES
26 Correct 5 ms 11436 KB answer = YES
27 Correct 4 ms 11352 KB answer = YES
28 Correct 5 ms 11356 KB answer = YES
29 Correct 5 ms 11352 KB answer = YES
30 Correct 4 ms 11356 KB answer = NO
31 Correct 5 ms 11280 KB answer = YES
32 Correct 5 ms 11356 KB answer = YES
33 Correct 5 ms 11360 KB answer = YES
34 Correct 5 ms 11368 KB answer = YES
35 Correct 6 ms 11368 KB answer = YES
36 Correct 5 ms 11352 KB answer = YES
37 Correct 5 ms 11356 KB answer = YES
38 Correct 5 ms 11452 KB answer = YES
39 Correct 5 ms 11356 KB answer = YES
40 Correct 6 ms 11352 KB answer = YES
41 Correct 5 ms 11356 KB answer = NO
42 Correct 5 ms 11356 KB answer = YES
43 Correct 5 ms 11448 KB answer = YES
44 Correct 6 ms 11356 KB answer = YES
45 Correct 5 ms 11356 KB answer = YES
46 Correct 5 ms 11356 KB answer = YES
47 Correct 5 ms 11352 KB answer = YES
48 Correct 5 ms 11356 KB answer = YES
49 Correct 12 ms 12296 KB answer = YES
50 Correct 12 ms 12636 KB answer = YES
51 Correct 12 ms 12808 KB answer = YES
52 Correct 8 ms 11868 KB answer = NO
53 Correct 5 ms 11356 KB answer = YES
54 Correct 6 ms 11612 KB answer = YES
55 Correct 8 ms 11864 KB answer = YES
56 Correct 12 ms 12300 KB answer = YES
57 Correct 11 ms 12124 KB answer = YES
58 Correct 10 ms 12124 KB answer = YES
59 Correct 11 ms 12120 KB answer = YES
60 Correct 11 ms 12124 KB answer = YES
61 Correct 8 ms 11868 KB answer = YES
62 Correct 46 ms 22868 KB answer = NO
63 Correct 63 ms 23748 KB answer = YES
64 Correct 46 ms 23664 KB answer = NO
65 Correct 55 ms 23728 KB answer = YES
66 Correct 6 ms 11352 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 4 ms 11408 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11352 KB answer = NO
5 Correct 5 ms 11352 KB answer = YES
6 Correct 4 ms 11384 KB answer = YES
7 Correct 4 ms 11356 KB answer = YES
8 Correct 5 ms 11356 KB answer = YES
9 Correct 4 ms 11352 KB answer = NO
10 Correct 4 ms 11356 KB answer = YES
11 Correct 4 ms 11356 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 4 ms 11356 KB answer = YES
14 Correct 4 ms 11240 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 4 ms 11356 KB answer = YES
17 Correct 4 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 4 ms 11352 KB answer = YES
20 Correct 5 ms 11356 KB answer = YES
21 Correct 4 ms 11356 KB answer = YES
22 Correct 5 ms 11356 KB answer = NO
23 Correct 4 ms 11352 KB answer = NO
24 Correct 5 ms 11356 KB answer = YES
25 Correct 4 ms 11356 KB answer = YES
26 Correct 5 ms 11436 KB answer = YES
27 Correct 4 ms 11352 KB answer = YES
28 Correct 5 ms 11356 KB answer = YES
29 Correct 5 ms 11352 KB answer = YES
30 Correct 4 ms 11356 KB answer = NO
31 Correct 5 ms 11280 KB answer = YES
32 Correct 5 ms 11356 KB answer = YES
33 Correct 5 ms 11360 KB answer = YES
34 Correct 5 ms 11368 KB answer = YES
35 Correct 6 ms 11368 KB answer = YES
36 Correct 5 ms 11352 KB answer = YES
37 Correct 5 ms 11356 KB answer = YES
38 Correct 5 ms 11452 KB answer = YES
39 Correct 5 ms 11356 KB answer = YES
40 Correct 6 ms 11352 KB answer = YES
41 Correct 5 ms 11356 KB answer = NO
42 Correct 5 ms 11356 KB answer = YES
43 Correct 5 ms 11448 KB answer = YES
44 Correct 6 ms 11356 KB answer = YES
45 Correct 5 ms 11356 KB answer = YES
46 Correct 5 ms 11356 KB answer = YES
47 Correct 5 ms 11352 KB answer = YES
48 Correct 5 ms 11356 KB answer = YES
49 Correct 12 ms 12296 KB answer = YES
50 Correct 12 ms 12636 KB answer = YES
51 Correct 12 ms 12808 KB answer = YES
52 Correct 8 ms 11868 KB answer = NO
53 Correct 5 ms 11356 KB answer = YES
54 Correct 6 ms 11612 KB answer = YES
55 Correct 8 ms 11864 KB answer = YES
56 Correct 12 ms 12300 KB answer = YES
57 Correct 11 ms 12124 KB answer = YES
58 Correct 10 ms 12124 KB answer = YES
59 Correct 11 ms 12120 KB answer = YES
60 Correct 11 ms 12124 KB answer = YES
61 Correct 8 ms 11868 KB answer = YES
62 Correct 46 ms 22868 KB answer = NO
63 Correct 63 ms 23748 KB answer = YES
64 Correct 46 ms 23664 KB answer = NO
65 Correct 55 ms 23728 KB answer = YES
66 Correct 6 ms 11352 KB answer = YES
67 Correct 82 ms 29112 KB answer = YES
68 Correct 73 ms 29128 KB answer = YES
69 Correct 73 ms 28868 KB answer = YES
70 Correct 120 ms 36564 KB answer = YES
71 Correct 75 ms 28968 KB answer = YES
72 Correct 99 ms 20168 KB answer = YES
73 Correct 86 ms 20028 KB answer = YES
74 Correct 58 ms 21452 KB answer = YES
75 Correct 24 ms 18032 KB answer = NO
76 Correct 12 ms 12540 KB answer = YES
77 Correct 22 ms 13524 KB answer = YES
78 Correct 34 ms 15100 KB answer = YES
79 Correct 69 ms 18896 KB answer = YES
80 Correct 69 ms 21580 KB answer = YES
81 Correct 43 ms 23216 KB answer = NO
82 Correct 93 ms 28240 KB answer = YES
83 Correct 106 ms 29576 KB answer = YES
84 Correct 102 ms 29640 KB answer = YES
85 Correct 83 ms 29128 KB answer = YES
86 Correct 95 ms 28912 KB answer = YES
87 Correct 41 ms 20836 KB answer = NO
88 Correct 98 ms 23496 KB answer = YES
89 Correct 74 ms 18504 KB answer = YES
90 Correct 80 ms 18524 KB answer = YES
91 Correct 86 ms 19124 KB answer = YES
92 Correct 40 ms 15780 KB answer = YES
93 Correct 43 ms 15572 KB answer = YES
94 Correct 51 ms 28332 KB answer = NO
95 Correct 38 ms 17796 KB answer = NO
96 Correct 139 ms 32072 KB answer = YES
97 Correct 34 ms 27600 KB answer = NO