Submission #680322

#TimeUsernameProblemLanguageResultExecution timeMemory
680322KG07Cijanobakterije (COCI21_cijanobakterije)C++14
27 / 70
93 ms14804 KiB
// Online C++ compiler to run C++ program online #include <bits/stdc++.h> using namespace std; vector<int> h[100000]; int a[100000]; bool b[100000]; int c[100000]; pair<int, int> d[100000]; int find(int x){ if(x == a[x])return x; else return a[x] = find(a[x]); } queue<pair<int, int>> q; int main() { // Write C++ code here int n, m; cin >> n >> m; for(int i = 1; i <= n; i++)a[i] = i; for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; h[u].push_back(v); h[v].push_back(u); b[find(u)] = true; a[find(u)] = find(v); } for(int i = 1; i <= n; i++){ if(b[i])continue; d[i] = {i, i}; for(int j = 0; j < h[i].size(); j++)q.push({h[i][j], i}); while(!q.empty()){ int u = q.front().first; int v = q.front().second; q.pop(); c[u] = c[v] + 1; if(c[u] > c[d[i].first])d[i].first = u; for(int j = 0; j < h[u].size(); j++)if(h[u][j] != v)q.push({h[u][j], u}); } c[d[i].first] = 0; d[i].second = d[i].first; for(int j = 0; j < h[d[i].first].size(); j++)q.push({h[d[i].first][j], d[i].first}); while(!q.empty()){ int u = q.front().first; int v = q.front().second; q.pop(); c[u] = c[v] + 1; if(c[u] > c[d[i].second])d[i].second = u; for(int j = 0; j < h[u].size(); j++)if(h[u][j] != v)q.push({h[u][j], u}); } } int s = 0; for(int i = 1; i <= n; i++){ //cout << i << " " << a[i] << " " << b[i] << " " << c[i] << " " << c[d[i].first] << " " << c[d[i].second] << "\n"; if(!b[i])s += c[d[i].second] + 1; } cout << s; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int j = 0; j < h[i].size(); j++)q.push({h[i][j], i});
      |                        ~~^~~~~~~~~~~~~
Main.cpp:38:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for(int j = 0; j < h[u].size(); j++)if(h[u][j] != v)q.push({h[u][j], u});
      |                            ~~^~~~~~~~~~~~~
Main.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j = 0; j < h[d[i].first].size(); j++)q.push({h[d[i].first][j], d[i].first});
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:49:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int j = 0; j < h[u].size(); j++)if(h[u][j] != v)q.push({h[u][j], u});
      |                            ~~^~~~~~~~~~~~~
#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...