Submission #745437

#	Time	Username	Problem	Language	Result	Execution time	Memory
745437		Tenis0206	Marshmallow Molecules (CCO19_day2problem2)	C++11	0 / 25	37 ms	8952 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e5;

int n,m;

int t[nmax + 5], rang[nmax + 5];

vector<int> l[nmax + 5];

int fr[nmax + 5];

int rep(int x)
{
    if(t[x]==x)
    {
        return x;
    }
    return rep(t[x]);
}

void uneste(int x, int y)
{
    x = rep(x);
    y = rep(y);
    if(x==y)
    {
        return;
    }
    if(rang[x] < rang[y])
    {
        swap(x,y);
    }
    t[y] = x;
    rang[x] += rang[y];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    #endif // home
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        l[x].push_back(y);
        l[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        sort(l[i].begin(),l[i].end());
    }
    for(int i=1;i<=n;i++)
    {
        rang[i] = 1, t[i] = i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<l[i].size();j++)
        {
            int nod = l[i][j];
            if(nod < i)
            {
                continue;
            }
            if(j < l[i].size() - 1)
            {
                uneste(l[i][j],l[i][j + 1]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ++fr[rep(i)];
    }
    int rez = m;
    for(int i=1;i<=n;i++)
    {
        rez += 1LL * fr[i] * (fr[i] - 1) / 2;
    }
    for(int i=1;i<=n;i++)
    {
        for(auto it : l[i])
        {
            if(it > i && rep(i) == rep(it))
            {
                --rez;
            }
        }
    }
    cout<<rez<<'\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j=0;j<l[i].size();j++)
      |                     ~^~~~~~~~~~~~
Main.cpp:74:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             if(j < l[i].size() - 1)
      |                ~~^~~~~~~~~~~~~~~~~

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