Submission #920947

#TimeUsernameProblemLanguageResultExecution timeMemory
920947simuyuMonthly railway pass (LMIO18_menesinis_bilietas)C++14
6 / 100
718 ms88300 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second vector<set<long> > adjs; // note that will have to findSet each of these. class UFDS { public: vector<long> parent, sizes; long num_sets; UFDS(long n) { for (long i=0; i<n; i++) { parent.push_back(i); } for (long i=0; i<n; i++) { sizes.push_back(1); } num_sets = n; } long findSet(long i) { if (parent[i] == i) return i; vector<long> elems; // path compression while (parent[i] != i) { elems.push_back(i); i = parent[i]; } for (long idx=0; idx<elems.size(); idx++) { parent[elems[i]] = i; } return i; } void unionSets(long i, long j) { //cout << "UNION " << i << ' ' << j << ": "; i = findSet(i); j = findSet(j); //cout << i << ' ' << j << "; "; if (i==j) return; if (sizes[i] < sizes[j]) swap(i, j); // so i >= j in size, not rlly depth but. parent[j] = i; // set parent //cout << sizes[i] << ' ' << sizes[j] << ": "; sizes[i] += sizes[j]; // update size sizes[j] = 0; // just in case ??? [ //cout << sizes[i] << ' ' << sizes[j] << "; "; // union the adjs for (auto it = adjs[j].begin(); it != adjs[j].end(); it++) { adjs[i].insert(*it); } adjs[j].clear(); // update number of sets num_sets --; // done :) } //long getSize(long s) return sizes[s]; }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // modifier ufds // store unordered set of neighbours of each edge and when union, combine them. long n, m; cin >> n >> m; for (long idx=0; idx<n; idx++) adjs.push_back(set<long>()); long i, j; char t; UFDS ufds(n); for (long idx=0; idx<m; idx++) { cin >> i >> j >> t; if (t=='A') { // add to adjs i = ufds.findSet(i-1); j = ufds.findSet(j-1); adjs[i].insert(j); adjs[j].insert(i); } else { // union the sets ufds.unionSets(i-1, j-1); } } // ufds done:) // check. /*cout << "UFDS DEBUG: \n"; cout << "PARENT: "; for (long i=0; i<n; i++) cout << ufds.parent[i] << ' '; cout << endl; cout << "SIZE: "; for (long i=0; i<n; i++) cout << ufds.sizes[i] << ' '; cout << endl; cout << "ADJ: " << endl; for (long i=0; i<n; i++) { cout << i << ": "; for (auto it=adjs[i].begin(); it!=adjs[i].end(); it++) { cout << *it << ' ' ; } cout << endl; } cout << endl << endl;*/ // get size of each component's adjs (rmbring to remove duplicates) long res=0; set<long> s; long temp; for (long i=0; i<n; i++) { //cout << i << ": "; for (auto it=adjs[i].begin(); it!=adjs[i].end(); it++) { temp = ufds.findSet(*it); if (temp != i) { s.insert(temp); } //s.insert(ufds.findSet(*it)); // add //cout << ufds.findSet(*it) << ' '; } //cout << endl; if (s.size() == ufds.num_sets-1) { //cout << "COUNTED: " << i << endl; res += ufds.sizes[i]; } s.clear(); // :) } cout << res << '\n'; return 0; }

Compilation message (stderr)

menesinis_bilietas.cpp: In member function 'long int UFDS::findSet(long int)':
menesinis_bilietas.cpp:31:29: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (long idx=0; idx<elems.size(); idx++) {
      |                          ~~~^~~~~~~~~~~~~
menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:138:22: warning: comparison of integer expressions of different signedness: 'std::set<long int>::size_type' {aka 'long unsigned int'} and 'long int' [-Wsign-compare]
  138 |         if (s.size() == ufds.num_sets-1) {
      |                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...