oj.uz

Submission #101455

# Submission time Handle Problem Language Result Execution time Memory
101455 2019-03-19T02:34:51 Z jamielim Adriatic (CEOI13_adriatic) C++14
25 / 100
 2000 ms 258988 KB 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    pair<pair<int,int>,int> arr[n];
    for(int i=0;i<n;i++){
        scanf("%d%d",&arr[i].first.first,&arr[i].first.second);
        arr[i].second=i;
    }
    sort(arr,arr+n);
    vector<int> adj[n];
    for(int i=0;i<n;i++){
        int j=i+1;
        while(j<n&&arr[i].first.first==arr[j].first.first)j++;
        for(;j<n;j++){
            if(arr[i].first.second<arr[j].first.second){
                adj[arr[i].second].push_back(arr[j].second);
                adj[arr[j].second].push_back(arr[i].second);
            }
        }
    }
    queue<int> q;
    int dist[n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)dist[j]=1000000010;
        dist[i]=0;
        q.push(i);
        while(!q.empty()){
            int cur=q.front();q.pop();
            for(int j=0;j<(int)adj[cur].size();j++){
                if(dist[adj[cur][j]]>dist[cur]+1){
                    dist[adj[cur][j]]=dist[cur]+1;
                    q.push(adj[cur][j]);
                }
            }
        }
        long long ans=0;
        for(int j=0;j<n;j++){
            ans+=dist[j];
        }
        printf("%lld\n",ans);
    }
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 1080 KB Output is correct
2 Execution timed out 2056 ms 7032 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 4984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 258988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 110100 KB Time limit exceeded
2 Halted 0 ms 0 KB -