oj.uz

Submission #209583

# Submission time Handle Problem Language Result Execution time Memory
209583 2020-03-14T17:52:30 Z gratus907 Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 7 ms 2552 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int ll
using pii = pair <int, int>;
#define INF 0x7f7f7f7f7f7f7f7f
const bool debug = false;
const int MX = 30202;

struct Edge
{
    int dest, w;
    bool operator<(const Edge &p) const
    {
        return w > p.w;
    }
};

bool relax(Edge edge, int u, int dist[])
{
    bool flag = 0;
    int v = edge.dest, w = edge.w;
    if (dist[v] > dist[u] + w && (dist[u]!=INF))
    {
        flag = true;
        dist[v] = dist[u]+w;
    }
    return flag;
}

void dijkstra(int dist[], int start, vector<Edge> graph[])
{
    fill(dist,dist+MX,INF);
    dist[start] = 0;
    priority_queue<Edge> pq;
    pq.push({start,0});
    while(!pq.empty())
    {
        Edge x = pq.top();
        int v = x.dest, w = x.w;
        pq.pop();
        if (w>dist[v])
            continue;
        for (auto ed : graph[v])
            if (relax(ed, v, dist))
                pq.push({ed.dest,dist[ed.dest]});
    }
}

int n, m;
vector <int> bi(30303, 0), pi(30303, 0);
vector <Edge> G[30303];
bitset <30303> mark[30303];
vector <int> doge[30303];
int distances[30303];
bool visit[30303];
void print_graph()
{
    for (int i = 0; i<n; i++)
    {
        for (auto it:G[i])
            printf("From %lld to %lld, %lld\n",i, it.dest, it.w);
    }
}
void print_dist()
{
    for (int i = 0; i<n; i++)
        printf("%lld ",distances[i]);
    printf("\n");
}
queue<pii> q;
int32_t main()
{
    cin >> n >> m;
    for (int i = 0; i<m; i++)
    {
        cin >> bi[i] >> pi[i];
        if (!mark[bi[i]][pi[i]] && i!=1)
        {
            mark[bi[i]][pi[i]] = true;
            doge[bi[i]].push_back(pi[i]);
        }
    }
    visit[bi[0]] = true;
    for (auto it:doge[bi[0]])
    {
        q.push({it, bi[0]});
    }
    memset(distances, 0x7f, sizeof(distances));
    distances[bi[0]] = 0;
    while (!q.empty())
    {
        auto dg = q.front();
        q.pop();
        mark[dg.second][dg.first] = true;
        for (int i = 1; ; i++)
        {
            int u = dg.second+i*dg.first;
            if (u >= n) break;

            if (!visit[u])
            {
                visit[u] = true;
                for (auto unseen:doge[u])
                {
                    q.push({unseen, u});
                }
            }
            if (!mark[u][dg.first])
            {
                mark[u][dg.first] = true;
                G[dg.second].push_back({u, i});
                distances[u] = min(distances[u], distances[dg.second]+i);
                //printf("Dist %lld renewed from %lld with %lld\n",u,dg.second,i);
                //printf("Dist %lld = %lld\n",u,distances[u]);
            }
            else break;
        }
        for (int i = -1; ; i--)
        {
            int u = dg.second+i*dg.first;
            if (u < 0) break;

            if (!visit[u])
            {
                visit[u] = true;
                for (auto unseen:doge[u])
                {
                    q.push({unseen, u});
                }
            }
            if (!mark[u][dg.first])
            {
                mark[u][dg.first] = true;
                G[dg.second].push_back({u, -i});
                distances[u] = min(distances[u], distances[dg.second]-i);
            }
            else break;
        }
    }
    //print_graph();
    //dijkstra(distances,bi[0],G);
    //print_dist();
    if (distances[bi[1]] >= INF)
    {
        printf("-1");
    }
    else
        printf("%lld\n",distances[bi[1]]);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 6 ms 2424 KB Output is correct
3 Correct 6 ms 2552 KB Output is correct
4 Correct 6 ms 2424 KB Output is correct
5 Correct 6 ms 2552 KB Output is correct
6 Correct 6 ms 2424 KB Output is correct
7 Incorrect 6 ms 2552 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2428 KB Output is correct
2 Correct 6 ms 2552 KB Output is correct
3 Correct 6 ms 2424 KB Output is correct
4 Correct 6 ms 2424 KB Output is correct
5 Correct 6 ms 2552 KB Output is correct
6 Correct 6 ms 2424 KB Output is correct
7 Incorrect 6 ms 2428 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2552 KB Output is correct
2 Correct 6 ms 2424 KB Output is correct
3 Correct 6 ms 2552 KB Output is correct
4 Correct 6 ms 2552 KB Output is correct
5 Correct 7 ms 2552 KB Output is correct
6 Correct 6 ms 2428 KB Output is correct
7 Incorrect 6 ms 2552 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 6 ms 2424 KB Output is correct
3 Correct 6 ms 2424 KB Output is correct
4 Correct 6 ms 2552 KB Output is correct
5 Correct 6 ms 2552 KB Output is correct
6 Correct 6 ms 2552 KB Output is correct
7 Incorrect 6 ms 2552 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 6 ms 2424 KB Output is correct
3 Correct 6 ms 2424 KB Output is correct
4 Correct 6 ms 2424 KB Output is correct
5 Correct 6 ms 2552 KB Output is correct
6 Correct 6 ms 2424 KB Output is correct
7 Incorrect 6 ms 2552 KB Output isn't correct
8 Halted 0 ms 0 KB -