Submission #718791

#	Time	Username	Problem	Language	Result	Execution time	Memory
718791		Charizard2021	Graph (BOI20_graph)	C++17	100 / 100	258 ms	13912 KiB

Graph

#include<bits/stdc++.h>
using namespace std;
const int N = 100001;
bool visited[N];
int sign[N];
int arr[N];
int val[N];
int val2[N];
int answer[N];
vector<pair<int, int> > adj[N];
int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		c *= 2;
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
	}
	for(int i = 1; i <= n; i++) {
		if(!visited[i]) {
			visited[i] = true;
            int idx = 0;
			sign[i] = 1;
			val[i] = 0;
			arr[idx] = i;
            idx++;
			bool bipartite = true;
			double x2;
            queue<int> q;
            q.push(i);
			while(!q.empty()) {
				int u = q.front();
                q.pop();
                for(pair<int, int> x : adj[u]){
                    int v = x.first;
                    int weight = x.second;
                    if(!visited[v]){
                        visited[v] = true;
                        sign[v] = -sign[u];
                        val[v] = weight - val[u];
                        arr[idx] = v;
                        idx++;
                        q.push(v);
                    }
                    else if(sign[v] == sign[u]){
                        bipartite = false;
                        x2 = (sign[v]) * (weight - val[v] - val[u])/2;
                    }
                }
			}
            if(bipartite){
                for(int j = 0; j < idx; j++){
                    int u = arr[j];
                    val2[j] = (-sign[u]) * val[u];
                }
                sort(val2, val2 + idx);
                x2 = val2[idx/2];
            }
            for(int j = 0; j < idx; j++){
                int u = arr[j];
                answer[u] = val[u] + sign[u] * x2;
            }
            for(int j = 0; j < idx; j++){
                int u = arr[j];
                for(pair<int, int> x : adj[u]){
                    int v = x.first;
                    if(answer[v] + answer[u] != x.second){
                        cout << "NO\n";
                        return 0;
                    }
                }
            }
		}
	}
    cout << "YES\n";
	for(int u = 1; u <= n; u++) {
        cout << 0.5 * answer[u] << " ";
	}
    cout << "\n";
}

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