Submission #1006901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006901		Unforgettablepl	IOI Fever (JOI21_fever)	C++17	37 / 100	5036 ms	374924 KiB

fever

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int,int>> points(n+1);
    for(int i=1;i<=n;i++)cin>>points[i].first>>points[i].second;
    for(int i=1;i<=n;i++){points[i].first*=2ll;points[i].second*=2ll;}
    vector<vector<pair<int,int>>> adj(4*n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j==i)continue;
            if(points[i].x==points[j].x and points[i].y>points[j].y){
                adj[4*i-1].emplace_back(4*j-2,(points[i].y-points[j].y)/2);
                adj[4*j-2].emplace_back(4*i-1,(points[i].y-points[j].y)/2);
            } else if(points[i].y==points[j].y and points[i].x<points[j].x){
                adj[4*i-3].emplace_back(4*j-4,(points[j].x-points[i].x)/2);
                adj[4*j-4].emplace_back(4*i-3,(points[j].x-points[i].x)/2);
            } else if(points[i].x<points[j].x and points[i].y>points[j].y){
                if(points[i].y-points[j].y!=points[j].x-points[i].x)continue;
                adj[4*i-1].emplace_back(4*j-4,points[i].y-points[j].y);
                adj[4*j-4].emplace_back(4*i-1,points[i].y-points[j].y);
                adj[4*i-3].emplace_back(4*j-2,points[i].y-points[j].y);
                adj[4*j-2].emplace_back(4*i-3,points[i].y-points[j].y);
            } else if(points[i].x<points[j].x and points[i].y<points[j].y){
                if(points[j].y-points[i].y!=points[j].x-points[i].x)continue;
                adj[4*i-2].emplace_back(4*j-4,points[j].y-points[i].y);
                adj[4*j-4].emplace_back(4*i-2,points[j].y-points[i].y);
                adj[4*i-3].emplace_back(4*j-1,points[j].y-points[i].y);
                adj[4*j-1].emplace_back(4*i-3,points[j].y-points[i].y);
            }
        }
    }
    int ans = 0;
    for(int i=0;i<4;i++){
        int siz = 0;
        vector<bool> visited(4*n);
        priority_queue<pair<int,int>> q;
        q.emplace(0,i);
        while(!q.empty()){
            auto [dist,idx] = q.top();q.pop();dist=-dist;
            if(visited[idx])continue;
            visited[idx]=true;
            siz++;
            for(auto[v,tim]:adj[idx])if(dist<=tim)q.emplace(-tim,v);
        }
        ans = max(ans,siz);
    }
    cout << ans << '\n';
}

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