Submission #797102

#	Time	Username	Problem	Language	Result	Execution time	Memory
797102		vjudge1	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	2 ms	4948 KiB

joitter2

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const ll N = 1e5, NS = 50 ;
ll ans, cnt[N + 1] ;
bool us[NS + 1][NS + 1] ;
map<pair<ll, ll>, bool> mp ;
vector<int> v[N + 1], v1[N + 1] ;
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    ll n, m ;
    cin >> n >> m ;
    if(n <= 50)
    {
        vector<pair<int, int>> pr ;
        while(m--)
        {
            ll a, b ;
            cin >> a >> b ;
            if(!mp[{a, b}])
            {
                ans++ ;
                mp[{a, b}] = 1 ;
//                cout << a<<"->"<< b << '\n' ;
                v[a].push_back(b) ;
                v1[b].push_back(a) ;
                if(mp[{b, a}])pr.push_back({a, b}) ;
            }
            bool flag = 1 ;
            while(flag)
            {
                flag = 0 ;
                for(auto i : pr)
                {
                    int y = i.fi, z = i.se ;
                    for(int j : v1[y])
                        if(j != z && !mp[{j, z}])
                        {
                            ans++ ;
                            flag = 1 ;
//                            cout << j<<"->"<< z << '\n' ;
                            v[j].push_back(z) ;
                            v1[z].push_back(j) ;
                            mp[{j, z}] = 1 ;
                        }
                    for(int j : v1[z])
                        if(j != y && !mp[{j, y}])
                        {
                            ans++ ;
                            flag = 1 ;
//                            cout << j<<"->"<< y << '\n' ;
                            v[j].push_back(y) ;
                            v1[y].push_back(j) ;
                            mp[{j, y}] = 1 ;
                        }
                }
            }
            cout << ans << '\n';
        }
        return 0 ;
    }
    if(n <= 2000)
    {
        while(m--)
        {
            ll x, y ;
            cin >> x >> y ;
            if(!mp[{x, y}])
            {
                ans++ ;
                mp[{x, y}] = 1 ;
                v[x].push_back(y) ;
                v1[y].push_back(x) ;
//                cout<<x<<"->"<<y << '\n' ;
            }
            deque<pair<int, int>> d ;
            if(mp[{x, y}] && mp[{y, x}])
                d.push_back({x, y}) ;
            while(d.size())
            {
                int x1 = d[0].fi, y1 = d[0].se ;
                d.pop_front() ;
                for(ll i = 0 ; i < v1[y1].size() ; i++)
                {
                    ll z = v1[y1][i] ;
                    if(z != x1 && !mp[{z, x1}])
                    {
                        mp[{z, x1}] = 1 ;
                        if(mp[{x1, z}])
                            d.push_back({z, x1}) ;
                        ans++ ;
                        v[z].push_back(x1) ;
//                        cout<<z<<"->"<<x1 << '\n' ;
                        v1[x1].push_back(z) ;
                    }
                }
                for(ll i = 0 ; i < v1[x1].size() ; i++)
                {
                    ll z = v1[x1][i] ;
                    if(z != y1 && !mp[{z, y1}])
                    {
                        mp[{z, y1}] = 1 ;
                        if(mp[{y1, z}])
                            d.push_back({z, y1}) ;
                        ans++ ;
                        v[z].push_back(y1) ;
//                        cout<<z<<"->"<<y1 << '\n' ;
                        v1[y1].push_back(z) ;
                    }
                }
                for(ll i = 0 ; i < v[y1].size() ; i++)
                {
                    ll z = v[y1][i] ;
                    if(z != x1 && !mp[{x1, z}] && mp[{z, y1}])
                    {
                        mp[{x1, z}] = 1 ;
                        ans++ ;
                        v[z].push_back(x1) ;
//                        cout<<z<<"->"<<x1 << '\n' ;
                        v1[x1].push_back(z) ;
                    }
                }
            }
            for(ll i = 0 ; i < v[y].size() ; i++)
            {
                ll z = v[y][i] ;
                if(z != x && !mp[{x, z}] && mp[{z, y}])
                {
                    mp[{x, z}] = 1 ;
                    ans++ ;
                    v[z].push_back(x) ;
//                        cout<<z<<"->"<<x << '\n' ;
                    v1[x].push_back(z) ;
                }
            }
            cout << ans << '\n' ;
        }
        return 0 ;
    }
    for(ll i = 1 ; i <= m ; i++)
    {
        ll x, y ;
        cin >> x >> y ;
        cout << ans << '\n' ;
    }
    return 0 ;
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:88:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                 for(ll i = 0 ; i < v1[y1].size() ; i++)
      |                                ~~^~~~~~~~~~~~~~~
joitter2.cpp:102:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |                 for(ll i = 0 ; i < v1[x1].size() ; i++)
      |                                ~~^~~~~~~~~~~~~~~
joitter2.cpp:116:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 for(ll i = 0 ; i < v[y1].size() ; i++)
      |                                ~~^~~~~~~~~~~~~~
joitter2.cpp:129:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |             for(ll i = 0 ; i < v[y].size() ; i++)
      |                            ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 16
• Subtask 3: 0 / 83