제출 #417538

#제출 시각아이디문제언어결과실행 시간메모리
417538albertolg101IOI 바이러스 (JOI21_fever)C++17
11 / 100
1 ms320 KiB
#include <bits/stdc++.h>

using namespace std;

#ifdef __local_leywar
#include <debug/debugger.h>
#endif

#define int long long
#define endl '\n'

const int INF = 2e9,
          MOD = 1e9+7,
          INFLL = 1e18;

using pii = pair<int, int>;
mt19937_64 rng(time(0));

pii operator - (pii a, pii b)
{
    return (pii){a.first - b.first, a.second - b.second};
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pii> ar(n);

    for(auto &i: ar)
        cin >> i.first >> i.second ; 

    for(int i = n - 1 ; i >= 0 ; i--)
    {
        ar[i] = ar[i] - ar[0];
    }


    int ans = 0;
    vector<int> dp(n, INFLL);
    vector<bool> flag(n);

    dp[0] = 0;

    while(true)
    {
        int dist = INFLL, nod = -1;

        //db(dp);

        for(int i = 0 ; i < n ; i++)
            if(!flag[i] and dp[i] < dist)
                dist = dp[i], nod = i;

        //db(dist, nod);

        if(nod == -1)
            break;

        ans++;
        flag[nod] = true;

        for(int i = 0 ; i < n ; i++)
        {
            pii temp = ar[nod] - ar[i];

            //db(ar[nod], ar[i], temp);
            //dbl(!flag[i], abs(temp.first) == abs(temp.second), dist <= abs(temp.first), dp[nod] > abs(temp.first));
            if(!flag[i] and abs(temp.first) == abs(temp.second) and dist <= abs(temp.first) and dp[i] > abs(temp.first))
                dp[i] = abs(temp.first);
        }
    }

    cout << ans ;

    return 0;
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...