oj.uz

Submission #42568

# Submission time Handle Problem Language Result Execution time Memory
42568 2018-02-28T08:52:21 Z nonocut Adriatic (CEOI13_adriatic) C++14
0 / 100
 2000 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define X first
#define Y second
const int inf = 1e9;
const int maxv = 2500;
const int maxn = 2.5e5 + 5;
struct node {
	int x,y,id;
};
int n;
node p[maxn];
int pos[maxv+5];
vector<pii> way[maxn];
deque<pii> dq;
int len[maxn][3];
bool cmp(node a, node b) {
	if(a.x!=b.x) return a.x<b.x;
	return a.y>b.y;
}
ll bfs(int u) {
    for(int i=1;i<=n;i++) if(i!=u) len[i][0] = len[i][1] = inf;
    dq.push_back({u,2});
    while(!dq.empty()) {
        int x = dq.front().X, d = dq.front().Y; dq.pop_front();
//        printf("%d %d : %d\n",x,d,len[x][d]);
        for(auto t : way[x]) {
            if(d==t.Y && len[t.X][t.Y]>len[x][d]) len[t.X][t.Y] = len[x][d], dq.push_front({t.X,t.Y});
            if(d!=t.Y && len[t.X][t.Y]>len[x][d]+1) len[t.X][t.Y] = len[x][d]+1, dq.push_back({t.X,t.Y});
        }
    }
    ll ans = 0;
    for(int i=1;i<=n;i++) if(i!=u) ans += min(len[i][0], len[i][1]);
    return ans;
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y), p[i].id = i;
	sort(&p[1],&p[n+1],cmp);
	for(int i=1;i<=n;i++) {
        int cur = 0;
        for(int y=p[i].y-1;y>=1;y--) {
            if(pos[y]>cur) {
                cur = pos[y];
                way[p[i].id].push_back({p[pos[y]].id,1});
                way[p[pos[y]].id].push_back({p[i].id,0});
            }
        }
        pos[p[i].y] = i;
	}
	for(int i=1;i<=n;i++) {
        printf("%lld\n",bfs(i));
	}
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:39:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
adriatic.cpp:40:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y), p[i].id = i;
                                                                  ^

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 7080 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 2013 ms 13172 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 2037 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -