| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 31057 |
2017-08-06T07:36:26 Z |
asdjke |
None (KOI16_dd) |
C++14 |
|
2000 ms |
29760 KB |
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;
class Obs{
public:
int x,yl,yh;
bool operator < (const Obs& b) const{
if(b.x > x) return true;
return false;
}
};
class State{
public:
int n,y;
long long c;
State(int n,int y,long long c){
this->n = n;
this->y = y;
this->c = c;
}
bool operator < (const State& b) const{
if(b.c < c) return true;
return false;
}
};
int N,sy,fx;
Obs A[100000];
vector<int> adj[100005];
set<int> v[100005],S;
long long fit;
int Seg[5000005];
int input(){
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);
}
sort(A,A+N);
return 0;
}
int init(){
int m = 0,p = 1;
for(int i=0;i<N;i++) if(m < A[i].yh) m = A[i].yh;
while(p <= m) p*=2;
int t,l,r;
for(int i=1;i<=p*2;i++) Seg[i] = N+1;
for(int i=N-1;i>=0;i--){
t = N+1;
l = p+A[i].yl;
while(l>=1){
t = min(t,Seg[l]);
l/=2;
}
adj[i+1].push_back(t);
t = N+1;
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 = N+1;
l = p+sy;
while(l>=1){
t = min(t,Seg[l]);
l/=2;
}
adj[0].push_back(t);
return 0;
}
int dijk(){
priority_queue<State,vector<State> > pq;
pq.push(State(0,sy,0));
while(!pq.empty()){
State ns = pq.top();
if(fit!=0 && ns.c > fit) break;
pq.pop();
if(ns.n == 0){
if(adj[0][0] == N+1){
pq.push(State(adj[0][0],sy,(long long)fx));
}
else{
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){
fit = ns.c;
S.insert(ns.y);
}
else{
if(fit == ns.c){
S.insert(ns.y);
}
}
continue;
}
if(v[ns.n].find(ns.y) != v[ns.n].end()) continue;
v[ns.n].insert(ns.y);
if(ns.y == A[ns.n-1].yl){
int togo = adj[ns.n][0];
long long toc;
if(togo == N+1) toc = ns.c + (long long)fx - (long long)A[ns.n-1].x;
else toc = ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x;
if(v[togo].find(ns.y) != v[togo].end()) continue;
pq.push(State(togo,ns.y,toc));
}
else if(ns.y == A[ns.n-1].yh){
int togo = adj[ns.n][1];
long long toc;
if(togo == N+1) toc = ns.c + (long long)fx - (long long)A[ns.n-1].x;
else toc = ns.c + (long long)A[togo-1].x - (long long)A[ns.n-1].x;
if(v[togo].find(ns.y) != v[togo].end()) continue;
pq.push(State(togo,ns.y,toc));
}
else{
int togo = adj[ns.n][0];
long long toc;
toc = ns.c + (long long)ns.y - (long long)A[ns.n-1].yl;
if(togo == N+1) toc += (long long)fx - (long long)A[ns.n-1].x;
else toc += (long long)A[togo-1].x - (long long)A[ns.n-1].x;
if(v[togo].find(A[ns.n-1].yl) == v[togo].end()){
pq.push(State(togo,A[ns.n-1].yl,toc));
}
togo = adj[ns.n][1];
toc = ns.c - (long long)ns.y + (long long)A[ns.n-1].yh;
if(togo == N+1) toc += (long long)fx - (long long)A[ns.n-1].x;
else toc += (long long)A[togo-1].x - (long long)A[ns.n-1].x;
if(v[togo].find(A[ns.n-1].yh) == v[togo].end()){
pq.push(State(togo,A[ns.n-1].yh,toc));
}
}
}
}
int main(){
input();
init();
dijk();
printf("%lld\n",fit);
printf("%d ",S.size());
for(auto i : S) printf("%d ",i);
}
Compilation message
dd.cpp: In function 'int dijk()':
dd.cpp:157:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
dd.cpp: In function 'int main()':
dd.cpp:164:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d ",S.size());
^
dd.cpp: In function 'int input()':
dd.cpp:38:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
dd.cpp:39: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:41: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 |
29760 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
29760 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
29760 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
29760 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
