oj.uz

Submission #801755

# Submission time Handle Problem Language Result Execution time Memory
801755 2023-08-02T07:29:31 Z 반딧불(#10089) IOI Fever (JOI21_fever) C++17
0 / 100
 2 ms 520 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll x[100002], y[100002];
int ans;

pair<int, ll> meet(int a, int d, int b){
    if(x[a]+y[a] == x[b]+y[b]){
        if(d==0 && x[a] < x[b]) return make_pair(3, x[b]-x[a]);
        if(d==3 && x[a] > x[b]) return make_pair(0, x[a]-x[b]);
        if(d==1 && x[a] < x[b]) return make_pair(2, x[b]-x[a]);
        if(d==2 && x[a] > x[b]) return make_pair(1, x[a]-x[b]);
    }
    if(x[a]-y[a] == x[b]-y[b]){
        if(d==0 && x[a] < x[b]) return make_pair(1, x[b]-x[a]);
        if(d==1 && x[a] > x[b]) return make_pair(0, x[a]-x[b]);
        if(d==2 && x[a] > x[b]) return make_pair(3, x[a]-x[b]);
        if(d==3 && x[a] < x[b]) return make_pair(2, x[b]-x[a]);
    }
    if(x[a] == x[b]){
        if(d==0 && x[a] < x[b]) return make_pair(2, (x[b]-x[a])/2);
        if(d==2 && x[a] > x[b]) return make_pair(0, (x[a]-x[b])/2);
    }
    if(y[a] == y[b]){
        if(d==1 && y[a] > y[b]) return make_pair(3, (y[a]-y[b])/2);
        if(d==3 && y[a] < y[b]) return make_pair(1, (y[b]-y[a])/2);
    }
    return make_pair(-1, -1);
}

bool visited[100002];

struct dat{
    int x, dir; ll d;
    dat(){}
    dat(int x, int dir, ll d): x(x), dir(dir), d(d){}
    bool operator<(const dat &r)const{
        return d>r.d;
    }
};

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &x[i], &y[i]);
        x[i]*=2, y[i]*=2;
    }

    for(int d=0; d<4; d++){
        priority_queue<dat> pq;
        for(int i=1; i<=n; i++) visited[i] = 0;
        pq.push(dat(1, d, 0));

        int cnt = 0;
        while(!pq.empty()){
            dat tmp = pq.top(); pq.pop();
            int x = tmp.x, dir = tmp.dir; ll d = tmp.d;
            if(visited[x]) continue;
            visited[x] = 1;
            cnt++;
            for(int y=1; y<=n; y++){
                if(visited[y]) continue;
                pair<int, ll> p = meet(x, dir, y);
                if(p.first != -1 && p.second < d) continue;
                pq.push(dat(y, p.first, p.second));
            }
        }
        ans = max(ans, cnt);
    }

    printf("%d", ans);
}

Compilation message

fever.cpp: In function 'int main()':
fever.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fever.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%lld %lld", &x[i], &y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -