oj.uz

답안 #220095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220095 2020-04-07T00:40:06 Z daniel920712 Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 937608 KB 
#include "walk.h"
#include <map>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
map < pair < long long , long long > , vector <  pair < long long , pair < long long , long long > > > > Next;
priority_queue < pair < long long , pair < long long , long long > > , vector < pair < long long , pair < long long , long long > > > , greater < pair < long long , pair < long long , long long > > > > all;
set < pair < long long , long long> > have;
vector < long long > xx[500005];
vector < long long > yy[500005];
bool F(long long a,long long b)
{
    return a<b;
}
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g)
{
    long long N=(long long) x.size(),M=(long long) l.size(),t,i,j;
    for(i=0;i<N;i++)
    {
        xx[i].push_back(0);
        xx[i].push_back(h[i]);
    }
    for(i=0;i<M;i++)
    {
        yy[i].push_back(x[l[i]]);
        yy[i].push_back(x[r[i]]);
    }
    for(i=0;i<M;i++)
    {
        for(j=l[i];j<=r[i];j++)
        {
            if(y[i]<=h[j])
            {
                xx[j].push_back(y[i]);
                yy[i].push_back(x[j]);
            }
        }
    }
    for(i=0;i<N;i++)
    {
        sort(xx[i].begin(),xx[i].end(),F);
        t=(long long) xx[i].size();
        for(j=1;j<t;j++)
        {
            //printf("aa %lld %lld %lld\n",x[i],xx[i][j-1],xx[i][j]);
            Next[make_pair(x[i],xx[i][j-1])].push_back(make_pair(xx[i][j]-xx[i][j-1],make_pair(x[i],xx[i][j])));
            Next[make_pair(x[i],xx[i][j])].push_back(make_pair(xx[i][j]-xx[i][j-1],make_pair(x[i],xx[i][j-1])));
        }
    }
    for(i=0;i<M;i++)
    {
        sort(yy[i].begin(),yy[i].end(),F);
        t=(long long) yy[i].size();
        for(j=1;j<t;j++)
        {
            //printf("bb %lld %lld %lld\n",y[i],yy[i][j-1],yy[i][j]);
            Next[make_pair(yy[i][j-1],y[i])].push_back(make_pair(yy[i][j]-yy[i][j-1],make_pair(yy[i][j],y[i])));
            Next[make_pair(yy[i][j],y[i])].push_back(make_pair(yy[i][j]-yy[i][j-1],make_pair(yy[i][j-1],y[i])));
        }
    }
    all.push(make_pair((long long)0,make_pair((long long)x[s],(long long)0)));
    while(!all.empty())
    {
        auto xx=all.top();
        all.pop();
        if(xx.second==make_pair((long long) x[g],(long long)0)) return xx.first;
        if(have.find(xx.second)!=have.end()) continue;
        have.insert(xx.second);
        //printf("%lld %lld %lld\n",xx.second.first,xx.second.second,xx.first);
        for(auto i:Next[xx.second]) all.push(make_pair(xx.first+i.first,i.second));
    }
	return -1;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 19 ms 24064 KB Output is correct
11 Correct 19 ms 23808 KB Output is correct
12 Correct 19 ms 23808 KB Output is correct
13 Correct 18 ms 23808 KB Output is correct
14 Correct 18 ms 23808 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 19 ms 23808 KB Output is correct
17 Correct 20 ms 24064 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 1468 ms 245268 KB Output is correct
4 Correct 2569 ms 281336 KB Output is correct
5 Correct 1124 ms 236408 KB Output is correct
6 Correct 1501 ms 214008 KB Output is correct
7 Correct 1096 ms 236828 KB Output is correct
8 Correct 2327 ms 299768 KB Output is correct
9 Correct 1422 ms 238024 KB Output is correct
10 Correct 3696 ms 354820 KB Output is correct
11 Correct 927 ms 157304 KB Output is correct
12 Correct 1086 ms 145144 KB Output is correct
13 Correct 3172 ms 329220 KB Output is correct
14 Correct 3201 ms 123552 KB Output is correct
15 Correct 2283 ms 131896 KB Output is correct
16 Correct 1075 ms 132460 KB Output is correct
17 Correct 996 ms 128732 KB Output is correct
18 Execution timed out 4077 ms 38020 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 62076 KB Output is correct
2 Execution timed out 4135 ms 937608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 340 ms 62076 KB Output is correct
2 Execution timed out 4135 ms 937608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 18 ms 23808 KB Output is correct
10 Correct 19 ms 24064 KB Output is correct
11 Correct 19 ms 23808 KB Output is correct
12 Correct 19 ms 23808 KB Output is correct
13 Correct 18 ms 23808 KB Output is correct
14 Correct 18 ms 23808 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 19 ms 23808 KB Output is correct
17 Correct 20 ms 24064 KB Output is correct
18 Correct 19 ms 23808 KB Output is correct
19 Correct 18 ms 23808 KB Output is correct
20 Correct 1468 ms 245268 KB Output is correct
21 Correct 2569 ms 281336 KB Output is correct
22 Correct 1124 ms 236408 KB Output is correct
23 Correct 1501 ms 214008 KB Output is correct
24 Correct 1096 ms 236828 KB Output is correct
25 Correct 2327 ms 299768 KB Output is correct
26 Correct 1422 ms 238024 KB Output is correct
27 Correct 3696 ms 354820 KB Output is correct
28 Correct 927 ms 157304 KB Output is correct
29 Correct 1086 ms 145144 KB Output is correct
30 Correct 3172 ms 329220 KB Output is correct
31 Correct 3201 ms 123552 KB Output is correct
32 Correct 2283 ms 131896 KB Output is correct
33 Correct 1075 ms 132460 KB Output is correct
34 Correct 996 ms 128732 KB Output is correct
35 Execution timed out 4077 ms 38020 KB Time limit exceeded
36 Halted 0 ms 0 KB -