oj.uz

Submission #595751

# Submission time Handle Problem Language Result Execution time Memory
595751 2022-07-14T06:01:55 Z 조영욱(#8444) IOI Fever (JOI21_fever) C++17
0 / 100
 5000 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
typedef pair<int,int> P;
P arr[16];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int dir[16];
int val[16];
int meet[16][16];
int dist[16];
bool vis[16];
const int INF=1e9+7;

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d %d",&arr[i].first,&arr[i].second);
    }
    for(int i=2;i<=n;i++) {
        if (arr[i].first>arr[1].first) {
            if (arr[i].second>arr[1].second) {
                dir[i]=2;
            }
            else {
                dir[i]=1;
            }
        }
        else {
            if (arr[i].second>arr[1].second) {
                dir[i]=3;
            }
            else {
                dir[i]=0;
            }
        }
    }
    int ret=0;
    for(int bit=0;bit<=(1<<n);bit++) {
        val[0]=bit%4;
        for(int i=2;i<=n;i++) {
            if (bit&(1<<i)) {
                val[i]=(dir[i]+1)%4;
            }
            else {
                val[i]=dir[i];
            }
        }
        memset(meet,-1,sizeof(meet));
        for(int i=1;i<=n;i++) {
            for(int j=i+1;j<=n;j++) {
                if ((val[i]+val[j])%2==0) {
                    continue;
                }
                int t=abs(arr[i].first-arr[j].first);
                if (arr[i].first+dx[val[i]]*t==arr[j].first+dx[val[j]]*t) {
                    if (arr[i].second+dy[val[i]]*t==arr[j].second+dy[val[j]]*t) {
                        meet[i][j]=t;
                        meet[j][i]=t;
                    }
                }
            }
        }
        dist[1]=0;
        dist[0]=INF;
        for(int i=2;i<=n;i++) {
            dist[i]=INF;
        }
        memset(vis,0,sizeof(vis));
        int x=0;
        for(int i=1;i<=n;i++) {
            int now=0;
            for(int j=1;j<=n;j++) {
                if (!vis[j]&&dist[j]<dist[now]) {
                    now=j;
                }
            }
            if (now==0) {
                break;
            }
            x++;
            vis[now]=true;
            for(int j=1;j<=n;j++) {
                if (!vis[j]&&meet[now][j]!=-1) {
                    dist[j]=min(dist[j],meet[now][j]);
                }
            }
        }
        ret=max(ret,x);
    }
    printf("%d",ret);
    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 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 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 212 KB Time limit exceeded
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 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 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 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 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 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 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 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -