oj.uz

답안 #1006741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006741 2024-06-24T08:02:08 Z Unforgettablepl IOI 바이러스 (JOI21_fever) C++17
0 / 100
 1 ms 428 KB 
#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*=2;points[i].second*=2;}
    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*n;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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -