oj.uz

Submission #906779

# Submission time Handle Problem Language Result Execution time Memory
906779 2024-01-15T01:26:03 Z Darren0724 Graph (BOI20_graph) C++17
100 / 100
 94 ms 24800 KB 
#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
namespace {
const int N=200005;
const int INF=1e9;
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 main1() {
    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;
    for(int i=1;i<=n;i++){
        if(ans[i]<0){
            cout<<'-';
        }
        cout<<abs(ans[i])/2<<'.'<<(ans[i]&1)*5<<' ';
    }
    cout<<endl;

    return 0;
}
}
int main(){
    main1();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8280 KB answer = YES
2 Correct 4 ms 8284 KB answer = YES
3 Correct 3 ms 8280 KB answer = YES
4 Correct 4 ms 8280 KB answer = NO
5 Correct 4 ms 8284 KB answer = YES
6 Correct 3 ms 8280 KB answer = YES
7 Correct 3 ms 8284 KB answer = YES
8 Correct 3 ms 8284 KB answer = YES
9 Correct 4 ms 8284 KB answer = NO
10 Correct 3 ms 8280 KB answer = YES
11 Correct 3 ms 8284 KB answer = YES
12 Correct 3 ms 8284 KB answer = NO
13 Correct 4 ms 8284 KB answer = YES
14 Correct 3 ms 8208 KB answer = YES
15 Correct 4 ms 8284 KB answer = YES
16 Correct 4 ms 8284 KB answer = YES
17 Correct 3 ms 8284 KB answer = YES
18 Correct 4 ms 8284 KB answer = YES
19 Correct 3 ms 8280 KB answer = YES
20 Correct 4 ms 8280 KB answer = YES
21 Correct 4 ms 8284 KB answer = YES
22 Correct 3 ms 8284 KB answer = NO
23 Correct 3 ms 8284 KB answer = NO
24 Correct 3 ms 8284 KB answer = YES
25 Correct 3 ms 8280 KB answer = YES
26 Correct 3 ms 8284 KB answer = YES
27 Correct 4 ms 8284 KB answer = YES
28 Correct 4 ms 8280 KB answer = YES
29 Correct 4 ms 8280 KB answer = YES
30 Correct 5 ms 8284 KB answer = NO
31 Correct 3 ms 8280 KB answer = YES
32 Correct 3 ms 8284 KB answer = YES
33 Correct 4 ms 8284 KB answer = YES
34 Correct 3 ms 8284 KB answer = YES
35 Correct 4 ms 8284 KB answer = YES
36 Correct 3 ms 8284 KB answer = YES
37 Correct 4 ms 8284 KB answer = YES
38 Correct 4 ms 8284 KB answer = YES
39 Correct 4 ms 8284 KB answer = YES
40 Correct 4 ms 8284 KB answer = YES
41 Correct 4 ms 8280 KB answer = NO
42 Correct 4 ms 8280 KB answer = YES
43 Correct 4 ms 8284 KB answer = YES
44 Correct 4 ms 8280 KB answer = YES
45 Correct 4 ms 8284 KB answer = YES
46 Correct 3 ms 8284 KB answer = YES
47 Correct 4 ms 8284 KB answer = YES
48 Correct 4 ms 8284 KB answer = YES
49 Correct 9 ms 8796 KB answer = YES
50 Correct 7 ms 9048 KB answer = YES
51 Correct 8 ms 9308 KB answer = YES
52 Correct 6 ms 8540 KB answer = NO
53 Correct 4 ms 8280 KB answer = YES
54 Correct 4 ms 8280 KB answer = YES
55 Correct 6 ms 8540 KB answer = YES
56 Correct 8 ms 8796 KB answer = YES
57 Correct 7 ms 8536 KB answer = YES
58 Correct 7 ms 8540 KB answer = YES
59 Correct 6 ms 8540 KB answer = YES
60 Correct 7 ms 8796 KB answer = YES
61 Correct 5 ms 8540 KB answer = YES
62 Correct 40 ms 12884 KB answer = NO
63 Correct 45 ms 13648 KB answer = YES
64 Correct 43 ms 13652 KB answer = NO
65 Correct 43 ms 13652 KB answer = YES
66 Correct 4 ms 8284 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8280 KB answer = YES
2 Correct 4 ms 8284 KB answer = YES
3 Correct 3 ms 8280 KB answer = YES
4 Correct 4 ms 8280 KB answer = NO
5 Correct 4 ms 8284 KB answer = YES
6 Correct 3 ms 8280 KB answer = YES
7 Correct 3 ms 8284 KB answer = YES
8 Correct 3 ms 8284 KB answer = YES
9 Correct 4 ms 8284 KB answer = NO
10 Correct 3 ms 8280 KB answer = YES
11 Correct 3 ms 8284 KB answer = YES
12 Correct 3 ms 8284 KB answer = NO
13 Correct 4 ms 8284 KB answer = YES
14 Correct 3 ms 8208 KB answer = YES
15 Correct 4 ms 8284 KB answer = YES
16 Correct 4 ms 8284 KB answer = YES
17 Correct 3 ms 8284 KB answer = YES
18 Correct 4 ms 8284 KB answer = YES
19 Correct 3 ms 8280 KB answer = YES
20 Correct 4 ms 8280 KB answer = YES
21 Correct 4 ms 8284 KB answer = YES
22 Correct 3 ms 8284 KB answer = NO
23 Correct 3 ms 8284 KB answer = NO
24 Correct 3 ms 8284 KB answer = YES
25 Correct 3 ms 8280 KB answer = YES
26 Correct 3 ms 8284 KB answer = YES
27 Correct 4 ms 8284 KB answer = YES
28 Correct 4 ms 8280 KB answer = YES
29 Correct 4 ms 8280 KB answer = YES
30 Correct 5 ms 8284 KB answer = NO
31 Correct 3 ms 8280 KB answer = YES
32 Correct 3 ms 8284 KB answer = YES
33 Correct 4 ms 8284 KB answer = YES
34 Correct 3 ms 8284 KB answer = YES
35 Correct 4 ms 8284 KB answer = YES
36 Correct 3 ms 8284 KB answer = YES
37 Correct 4 ms 8284 KB answer = YES
38 Correct 4 ms 8284 KB answer = YES
39 Correct 4 ms 8284 KB answer = YES
40 Correct 4 ms 8284 KB answer = YES
41 Correct 4 ms 8280 KB answer = NO
42 Correct 4 ms 8280 KB answer = YES
43 Correct 4 ms 8284 KB answer = YES
44 Correct 4 ms 8280 KB answer = YES
45 Correct 4 ms 8284 KB answer = YES
46 Correct 3 ms 8284 KB answer = YES
47 Correct 4 ms 8284 KB answer = YES
48 Correct 4 ms 8284 KB answer = YES
49 Correct 9 ms 8796 KB answer = YES
50 Correct 7 ms 9048 KB answer = YES
51 Correct 8 ms 9308 KB answer = YES
52 Correct 6 ms 8540 KB answer = NO
53 Correct 4 ms 8280 KB answer = YES
54 Correct 4 ms 8280 KB answer = YES
55 Correct 6 ms 8540 KB answer = YES
56 Correct 8 ms 8796 KB answer = YES
57 Correct 7 ms 8536 KB answer = YES
58 Correct 7 ms 8540 KB answer = YES
59 Correct 6 ms 8540 KB answer = YES
60 Correct 7 ms 8796 KB answer = YES
61 Correct 5 ms 8540 KB answer = YES
62 Correct 40 ms 12884 KB answer = NO
63 Correct 45 ms 13648 KB answer = YES
64 Correct 43 ms 13652 KB answer = NO
65 Correct 43 ms 13652 KB answer = YES
66 Correct 4 ms 8284 KB answer = YES
67 Correct 47 ms 21964 KB answer = YES
68 Correct 50 ms 21948 KB answer = YES
69 Correct 47 ms 21704 KB answer = YES
70 Correct 72 ms 24800 KB answer = YES
71 Correct 47 ms 21700 KB answer = YES
72 Correct 53 ms 13004 KB answer = YES
73 Correct 54 ms 12744 KB answer = YES
74 Correct 34 ms 15748 KB answer = YES
75 Correct 22 ms 12892 KB answer = NO
76 Correct 8 ms 8796 KB answer = YES
77 Correct 13 ms 9464 KB answer = YES
78 Correct 22 ms 10464 KB answer = YES
79 Correct 43 ms 12408 KB answer = YES
80 Correct 40 ms 15952 KB answer = YES
81 Correct 34 ms 16720 KB answer = NO
82 Correct 50 ms 20936 KB answer = YES
83 Correct 55 ms 21704 KB answer = YES
84 Correct 57 ms 21960 KB answer = YES
85 Correct 49 ms 21968 KB answer = YES
86 Correct 47 ms 21940 KB answer = YES
87 Correct 35 ms 14168 KB answer = NO
88 Correct 61 ms 16076 KB answer = YES
89 Correct 40 ms 11600 KB answer = YES
90 Correct 44 ms 11600 KB answer = YES
91 Correct 41 ms 11600 KB answer = YES
92 Correct 22 ms 10720 KB answer = YES
93 Correct 22 ms 10460 KB answer = YES
94 Correct 44 ms 21192 KB answer = NO
95 Correct 48 ms 11604 KB answer = NO
96 Correct 94 ms 20940 KB answer = YES
97 Correct 33 ms 21200 KB answer = NO