Submission #1181507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181507		meicris	Marshmallow Molecules (CCO19_day2problem2)	C++17	25 / 25	62 ms	10568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
set<long> grafo[100005];
void solve(){
    long cont=0;
    long n,q,a,b,sg;
    cin>>n>>q;
    while(q--)
    {
        cin>>a>>b;
        grafo[a].insert(b);
    }
    for(long i=1;i<=n;i++)
    {
        if(!grafo[i].empty()){
            cont+=grafo[i].size();
            sg=*grafo[i].begin();
            grafo[i].erase(grafo[i].begin());
            if(grafo[i].size() > grafo[sg].size()) grafo[sg].swap(grafo[i]);
            for(auto x:grafo[i]) grafo[sg].insert(x);
        }
        grafo[i].clear();
    }
    cout<<cont;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 10 / 10