Submission #417538

#	Time	Username	Problem	Language	Result	Execution time	Memory
417538		albertolg101	IOI Fever (JOI21_fever)	C++17	11 / 100	1 ms	320 KiB

fever

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31