Submission #101503

#TimeUsernameProblemLanguageResultExecution timeMemory
101503cheehengAdriatic (CEOI13_adriatic)C++14
0 / 100
281 ms60668 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; int R[250000]; int C[250000]; int dist[250000]; vector<int> AdjList[250005]; vector<int> AdjList2[250005]; ii EdgeList[250005]; int rank1[250005]; int p[250005]; void init(int N){ for(int i = 0; i < N; i ++){ rank1[i] = 0; p[i] = i; } } int findSet(int i){ return (p[i] == i) ? i : (p[i] = findSet(p[i])); } bool isSameSet(int i, int j){ return findSet(i) == findSet(j); } void unionSet(int i, int j){ if(!isSameSet(i, j)){ int x = findSet(i); int y = findSet(j); if(rank1[x] > rank1[y]){ p[y] = x; }else{ p[x] = y; if(rank1[x] == rank1[y]){rank1[y] ++;} } } } int main(){ int N; scanf("%d", &N); for(int i = 0; i < N; i ++){ scanf("%d%d", &R[i], &C[i]); } int cnt = 0; for(int i = 0; i < N; i ++){ for(int j = i+1; j < N; j ++){ if((R[i] < R[j] && C[i] < C[j]) || (R[i] > R[j] && C[i] > C[j])){ AdjList[i].push_back(j); AdjList[j].push_back(i); EdgeList[cnt ++] = ii(i, j); } } } random_shuffle(EdgeList, EdgeList+cnt); // prevent worst-case time complexity init(N); int taken = 0; for(int i = 0; i < cnt && taken < N-1; i ++){ int u = EdgeList[i].first; int v = EdgeList[i].second; if(!isSameSet(u, v) || taken >= N-1){ unionSet(u, v); AdjList2[u].push_back(v); AdjList2[v].push_back(u); taken ++; } } random_shuffle(EdgeList, EdgeList+cnt); for(int i = 0; i < 0.5*cnt; i ++){ int u = EdgeList[i].first; int v = EdgeList[i].second; if(1){ //unionSet(u, v); AdjList2[u].push_back(v); AdjList2[v].push_back(u); taken ++; } } for(int i = 0; i < N; i ++){ long long ans = 0; memset(dist, -1, sizeof(dist)); queue<int> q; q.push(i); dist[i] = 0; while(!q.empty()){ int u = q.front(); q.pop(); for(int v: AdjList2[u]){ if(dist[v] == -1){ dist[v] = dist[u] + 1; q.push(v); } } } for(int j = 0; j < N; j ++){ ans += dist[j]; } printf("%lld\n", ans); } }

Compilation message (stderr)

adriatic.cpp: In function 'int main()':
adriatic.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
adriatic.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &R[i], &C[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...