Submission #556434

#	Time	Username	Problem	Language	Result	Execution time	Memory
556434		fuad27	Graph (BOI20_graph)	C++17	5 / 100	28 ms	632 KiB

Graph

        #include<bits/stdc++.h>
        using namespace std;
        struct edge {
        	int u=0, v=0, type=0;
        };
        const int MAXN = 6, MAXM = 15;
        int n, m;
        vector<edge> e(MAXM);
        vector<int> curr(MAXN);
        vector<pair<long long, vector<int>>> answers; 
        bool brute(int in, long long sum) {
        	if(in == n) {
        		for(int i = 0;i<m;i++) {
        			if(curr[e[i].u] + curr[e[i].v] != 2*e[i].type)return false;
        		}
        		answers.push_back(make_pair(sum, curr));
        		return true;
        	}
        	else {
        		bool check = false;
        		for(int i = -10;i<=10;i++) {
        			curr[in] = i;
        			check|=brute(in+1, sum+abs(i));
        		}
        		return check;
        	}
        }
        int main () {
        	cin >> n >> m;
        	for(int i = 0;i<m;i++) {
        		cin >> e[i].u >> e[i].v >> e[i].type;
        		e[i].u--, e[i].v--;
        	}
        	if(n <= 5 and m<=14) {
        		if(!brute(0, 0))cout << "NO\n";
        		else {
        			sort(answers.begin(), answers.end());
        			cout << "YES\n";
        			for(int i = 0;i<n;i++) {
        				cout << 0.5*answers[0].second[i] << " ";
        			}
        			cout << "\n";
        		}	
        	}
        }

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