Submission #821257

#TimeUsernameProblemLanguageResultExecution timeMemory
821257DobromirAngelovMarshmallow Molecules (CCO19_day2problem2)C++14
0 / 25
4 ms5160 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN=1e5+5; int n,m; vector<int> adj[MAXN]; bool used[MAXN]; long long ans=0; bool g[105][105]; void solve(int v) { used[v]=1; priority_queue<int> pq; pq.push(-v); while(!pq.empty()) { v=-pq.top(); pq.pop(); int bef=pq.size(); int br=0; for(int i=0;i<adj[v].size();i++) { if(!used[adj[v][i]]) { used[adj[v][i]]=1; pq.push(-adj[v][i]); br++; } } ans+=br; ans+=(long long) br*bef; ans+=(long long) br*(br-1)/2; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(int i=0;i<m;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); g[u][v]=1; } /* if(n<=100) { for(int i=1;i<=n;i++) { vector<int> v; for(int j=i+1;j<=n;j++) { if(g[i][j]) v.push_back(j); } for(int j=0;j<v.size();j++) { for(int k=j+1;k<v.size();k++) { g[v[j]][v[k]]=1; } } } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) if(g[i][j]) ans++; } cout<<ans<<endl; return 0; }*/ for(int i=1;i<=n;i++) { if(!used[i]) { if(adj[i].size()==0) continue; solve(i); } } cout<<ans<<endl; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void solve(int)':
Main.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i=0;i<adj[v].size();i++)
      |                     ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...