oj.uz

Submission #906777

# Submission time Handle Problem Language Result Execution time Memory
906777 2024-01-15T01:20:57 Z Darren0724 Graph (BOI20_graph) C++17
5 / 100
 5 ms 11356 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;
    for(int i=1;i<=n;i++){
        if(ans[i]<0)cout<<'-';
        cout<<ans[i]/2<<"."<<(ans[i]&1)*5<<' ';
    }
    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 5 ms 11356 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11356 KB answer = NO
5 Correct 5 ms 11356 KB answer = YES
6 Correct 5 ms 11356 KB answer = YES
7 Correct 5 ms 11356 KB answer = YES
8 Correct 4 ms 11356 KB answer = YES
9 Correct 4 ms 11356 KB answer = NO
10 Correct 5 ms 11356 KB answer = YES
11 Correct 4 ms 11352 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 5 ms 11356 KB answer = YES
14 Correct 4 ms 11356 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 5 ms 11304 KB answer = YES
17 Correct 5 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 5 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 5 ms 11356 KB answer = NO

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 5 ms 11356 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11356 KB answer = NO
5 Correct 5 ms 11356 KB answer = YES
6 Correct 5 ms 11356 KB answer = YES
7 Correct 5 ms 11356 KB answer = YES
8 Correct 4 ms 11356 KB answer = YES
9 Correct 4 ms 11356 KB answer = NO
10 Correct 5 ms 11356 KB answer = YES
11 Correct 4 ms 11352 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 5 ms 11356 KB answer = YES
14 Correct 4 ms 11356 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 5 ms 11304 KB answer = YES
17 Correct 5 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 5 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 5 ms 11356 KB answer = NO
24 Incorrect 5 ms 11356 KB Expected double, but "--1.0" found
25 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 5 ms 11356 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11356 KB answer = NO
5 Correct 5 ms 11356 KB answer = YES
6 Correct 5 ms 11356 KB answer = YES
7 Correct 5 ms 11356 KB answer = YES
8 Correct 4 ms 11356 KB answer = YES
9 Correct 4 ms 11356 KB answer = NO
10 Correct 5 ms 11356 KB answer = YES
11 Correct 4 ms 11352 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 5 ms 11356 KB answer = YES
14 Correct 4 ms 11356 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 5 ms 11304 KB answer = YES
17 Correct 5 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 5 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 5 ms 11356 KB answer = NO
24 Incorrect 5 ms 11356 KB Expected double, but "--1.0" found
25 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 5 ms 11356 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11356 KB answer = NO
5 Correct 5 ms 11356 KB answer = YES
6 Correct 5 ms 11356 KB answer = YES
7 Correct 5 ms 11356 KB answer = YES
8 Correct 4 ms 11356 KB answer = YES
9 Correct 4 ms 11356 KB answer = NO
10 Correct 5 ms 11356 KB answer = YES
11 Correct 4 ms 11352 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 5 ms 11356 KB answer = YES
14 Correct 4 ms 11356 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 5 ms 11304 KB answer = YES
17 Correct 5 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 5 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 5 ms 11356 KB answer = NO
24 Incorrect 5 ms 11356 KB Expected double, but "--1.0" found
25 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 5 ms 11356 KB answer = YES
3 Correct 5 ms 11356 KB answer = YES
4 Correct 4 ms 11356 KB answer = NO
5 Correct 5 ms 11356 KB answer = YES
6 Correct 5 ms 11356 KB answer = YES
7 Correct 5 ms 11356 KB answer = YES
8 Correct 4 ms 11356 KB answer = YES
9 Correct 4 ms 11356 KB answer = NO
10 Correct 5 ms 11356 KB answer = YES
11 Correct 4 ms 11352 KB answer = YES
12 Correct 5 ms 11356 KB answer = NO
13 Correct 5 ms 11356 KB answer = YES
14 Correct 4 ms 11356 KB answer = YES
15 Correct 4 ms 11356 KB answer = YES
16 Correct 5 ms 11304 KB answer = YES
17 Correct 5 ms 11356 KB answer = YES
18 Correct 5 ms 11356 KB answer = YES
19 Correct 5 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 5 ms 11356 KB answer = NO
24 Incorrect 5 ms 11356 KB Expected double, but "--1.0" found
25 Halted 0 ms 0 KB -