You are viewing a single comment's thread. Return to all comments →
Solution in C++
#include <bits/stdc++.h> using namespace std; #define FOR(i, n) for(int i = 0; i < n; ++i) #define pb push_back vector<string> split_string(string); int get(int n, vector<vector<int>> limit){ vector<vector<int>> edges; int v = n + 1; FOR(x, n){ vector<int> temp1, temp2; temp1.pb(x + 1); temp1.pb(x); temp1.pb(0); temp2.pb(x); temp2.pb(x + 1); temp2.pb(1); edges.pb(temp1); edges.pb(temp2); temp1.clear(); temp2.clear(); } FOR(x, n + 1){ vector<int> temp1; temp1.pb(v); temp1.pb(x); temp1.pb(0); edges.pb(temp1); temp1.clear(); } FOR(i, limit.size()){ vector<int> temp1, temp2; temp1.pb(limit[i][0] - 1); temp1.pb(limit[i][1]); temp1.pb(limit[i][2]); temp2.pb(limit[i][1]); temp2.pb(limit[i][0] - 1); temp2.pb(-limit[i][2]); edges.pb(temp1); edges.pb(temp2); temp1.clear(); temp2.clear(); } vector<int> dist(n + 2); fill(dist.begin(), dist.end(), 10000000000); dist[v] = 0; FOR(x, n + 1){ FOR(i, edges.size()){ dist[edges[i][1]] = min(dist[edges[i][1]], dist[edges[i][0]] + edges[i][2]); } } return dist[n] - dist[0]; } vector<int> liars(int n, vector<vector<int>> sets) { vector<vector<int>> rev; FOR(i, sets.size()){ int temp = sets[i][1] - sets[i][0] + 1 - sets[i][2]; vector<int> tmp1; tmp1.pb(sets[i][0]); tmp1.pb(sets[i][1]); tmp1.pb(temp); rev.pb(tmp1); tmp1.clear(); } vector<int> ret; ret.pb(get(n, sets)); ret.pb(n - get(n, rev)); return ret; } int main(){ ofstream fout(getenv("OUTPUT_PATH")); string nm_temp; getline(cin, nm_temp); vector<string> nm = split_string(nm_temp); int n = stoi(nm[0]); int m = stoi(nm[1]); vector<vector<int>> sets(m); for (int sets_row_itr = 0; sets_row_itr < m; sets_row_itr++) { sets[sets_row_itr].resize(3); for (int sets_column_itr = 0; sets_column_itr < 3; sets_column_itr++) { cin >> sets[sets_row_itr][sets_column_itr]; } cin.ignore(numeric_limits<streamsize>::max(), '\n'); } vector<int> result = liars(n, sets); for (int result_itr = 0; result_itr < result.size(); result_itr++) { fout << result[result_itr]; if (result_itr != result.size() - 1) { fout << " "; } } fout << "\n"; fout.close(); return 0; } vector<string> split_string(string input_string) { string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) { return x == y and x == ' '; }); input_string.erase(new_end, input_string.end()); while (input_string[input_string.length() - 1] == ' ') { input_string.pop_back(); } vector<string> splits; char delimiter = ' '; size_t i = 0; size_t pos = input_string.find(delimiter); while (pos != string::npos) { splits.push_back(input_string.substr(i, pos - i)); i = pos + 1; pos = input_string.find(delimiter, i); } splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1)); return splits; }
Seems like cookies are disabled on this browser, please enable them to open this website
Liars
You are viewing a single comment's thread. Return to all comments →
Solution in C++