| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 31055 |
2017-08-06T06:49:04 Z |
asdjke |
None (KOI16_dd) |
C++11 |
|
2000 ms |
40700 KB |
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<map>
#define INF 1000000
using namespace std;
class Obstacle{
public:
int x,yl,yh;
bool operator < (const Obstacle & b) const{
if(b.x > x) return true;
return false;
}
};
class State{
public:
int n,ny;
long long c;
State(int x=0,int y=0,long long z=0){
this->n = x;
this->ny = y;
this->c = z;
}
bool operator < (const State& b) const{
if(b.c < c) return true;
return false;
}
};
int N,sy,fx;
Obstacle A[100000];
int Seg[9000005];
vector<int> adj[100005];
map<pair<int,int>,int> M;
set<int> S;
int fit;
priority_queue<State,vector<State> > pq;
int dijk(){
pq.push(State(0,sy,0));
while(!pq.empty()){
State ns = pq.top();
pq.pop();
if(ns.n == 0){
if(adj[0][0] == N+1){
pq.push(State(adj[0][0],sy,(long long)fx));
continue;
}
pq.push(State(adj[0][0],sy,(long long)A[adj[0][0]-1].x));
continue;
}
if(ns.n == N+1){
if(S.size() == 0){
S.insert(ns.ny);
fit = ns.c;
}
else{
if(ns.c > fit) continue;
else{
S.insert(ns.ny);
}
}
continue;
}
if(M.find({ns.n,ns.ny}) != M.end()) continue;
M[{ns.n,ns.ny}] = 1;
if(ns.ny == A[ns.n-1].yl){
int togo = adj[ns.n][0],toy = ns.ny;
if(M.find({togo,toy}) != M.end()) continue;
if(togo == N+1){
pq.push(State(togo,toy,ns.c + (long long)fx - (long long)A[ns.n-1].x));
}
else pq.push(State(togo,toy,ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x));
}
else if(ns.ny == A[ns.n-1].yh){
int togo = adj[ns.n][1],toy = ns.ny;
if(M.find({togo,toy}) != M.end()) continue;
if(togo == N+1){
pq.push(State(togo,toy,ns.c + (long long)fx - (long long)A[ns.n-1].x));
}
else pq.push(State(togo,toy,ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x));
}
else{
if(M.find({ns.n,A[ns.n-1].yl}) == M.end()){
pq.push(State(ns.n,A[ns.n-1].yl,ns.c + (long long)ns.ny - (long long)A[ns.n-1].yl));
}
if(M.find({ns.n,A[ns.n-1].yh}) == M.end()){
pq.push(State(ns.n,A[ns.n-1].yh,ns.c - (long long)ns.ny + (long long)A[ns.n-1].yh));
}
}
}
}
int init(){
int m = 0,p = 1;
scanf("%d",&N);
scanf("%d%d",&sy,&fx);
for(int i=0;i<N;i++){
scanf("%d%d%d",&A[i].x,&A[i].yl,&A[i].yh);
m = max(m,A[i].yh);
}
sort(A,A+N);
while(p<=m) p*=2;
for(int i=1;i<=p*2;i++) Seg[i] = N+1;
int l,r,t;
for(int i=N-1;i>=0;i--){
t = INF;
l = p+A[i].yl;
while(l>=1){
t = min(t,Seg[l]);
l/=2;
}
adj[i+1].push_back(t);
t = INF;
l = p+A[i].yh;
while(l>=1){
t = min(t,Seg[l]);
l/=2;
}
adj[i+1].push_back(t);
l = p+A[i].yl;
r = p+A[i].yh;
while(l<=r){
if(l%2==1){
Seg[l] = i+1;
l++;
}
if(r%2==0){
Seg[r] = i+1;
r--;
}
l/=2;
r/=2;
}
}
t = INF;
l = p+sy;
while(l>=1){
t = min(t,Seg[l]);
l/=2;
}
adj[0].push_back(t);
}
int main(){
init();
dijk();
printf("%d\n%d ",fit,S.size());
for(auto i : S){
printf("%d ",i);
}
}
Compilation message
dd.cpp: In function 'int dijk()':
dd.cpp:94:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
dd.cpp: In function 'int init()':
dd.cpp:145:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
dd.cpp: In function 'int main()':
dd.cpp:150:34: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::set<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n%d ",fit,S.size());
^
dd.cpp: In function 'int init()':
dd.cpp:98:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
dd.cpp:99:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&sy,&fx);
^
dd.cpp:101:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&A[i].x,&A[i].yl,&A[i].yh);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
40700 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
40700 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
40700 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
40700 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
