oj.uz

Submission #869110

# Submission time Handle Problem Language Result Execution time Memory
869110 2023-11-03T08:29:01 Z Eliorita Toll (BOI17_toll) C++14
7 / 100
 63 ms 94292 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define x first
#define y second
#define getbit(u,i) ((u>>i)&1)
#define all(x) x.begin(),x.end()
#define N 200001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int k,m,n,q,h[N],p[50010][17][6],s[50010][17][6],d[N],cur[6],nxt[6];
vector<ii> g[N],f[N];
vector<int> del;
const int inf=4557430888798830399;
void init()
{
    for(int i=0;i<n;i++) h[i]=i/k+1;
    for(int dep=n/k;dep>=0;dep--)
    {
        for(int u=dep*k;u<=dep*k+k-1;u++)
        {
            for(ii v : g[u])
            {
                p[u][0][v.x%k]=v.x;
                s[u][0][v.x%k]=v.y;
            }
            for(int i=1;i<=16;i++)
            {
                for(int j=0;j<k;j++)
                {
                    for(int l=0;l<k;l++)
                    {
                        if(p[u][i-1][l]!=inf&&p[p[u][i-1][l]][i-1][j]!=inf)
                        {
                            p[u][i][j]=p[p[u][i-1][l]][i-1][j];
                            s[u][i][j]=min(s[u][i][j],s[u][i-1][l]+s[p[u][i-1][l]][i-1][j]);
                        }
                    }
                }
            }
        }
    }
}
priority_queue<ii,vector<ii>,greater<ii>> pq;
void dijkstra(int u)
{
    d[u]=0;
    pq.push({0,u});
    while(!pq.empty())
    {
        int u=pq.top().y;
        int du=pq.top().x;
        pq.pop();
        if(du!=d[u]) continue;
        for(ii e : f[u])
        {
            int v=e.y,dv=e.x;
            if(d[v]>du+dv)
            {
                d[v]=du+dv;
                pq.push({d[v],v});
            }
        }
    }
}
void get(int u,int v)
{
    int base=h[v]-h[u];
    for(int i=0;i<k;i++) cur[i]=i+(u/k)*k;
    d[v]=inf;
    for(int i=16;i>=0;i--)
    {
        if(getbit(base,i))
        {
            for(int j=0;j<k;j++)
            {
                if(cur[j]!=inf)
                {
                    for(int l=0;l<k;l++)
                    {
                        if(s[cur[j]][i][l]!=inf)
                        {
                            del.push_back(cur[j]);
                            nxt[l]=1;
                            f[cur[j]].pb({s[cur[j]][i][l],p[cur[j]][i][l]});
                        }
                    }
                }
            }
            for(int j=0;j<k;j++)
            {
                if(nxt[j]&&cur[j]!=inf)
                {
                    cur[j]+=(1<<i)*k;
                    d[cur[j]]=inf;
                }
                else cur[j]=inf;
                nxt[j]=0;
            }
        }
    }
    dijkstra(u);
    for(int u : del) f[u].clear();
    del.clear();
    if(d[v]==inf) cout<<-1<<'\n';
    else cout<<d[v]<<'\n';
}
signed main()
{
    if(fopen("demo.inp","r"))
    {
        freopen("demo.inp","r",stdin);
        freopen("demo.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>k>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].pb({v,w});
    }
    memset(p,0x3f,sizeof(p));
    memset(s,0x3f,sizeof(s));
    init();
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        get(u,v);
    }
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("demo.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("demo.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94292 KB Output is correct
2 Correct 11 ms 91380 KB Output is correct
3 Correct 12 ms 91084 KB Output is correct
4 Correct 12 ms 91228 KB Output is correct
5 Correct 12 ms 91128 KB Output is correct
6 Correct 12 ms 91224 KB Output is correct
7 Correct 12 ms 91228 KB Output is correct
8 Correct 44 ms 93104 KB Output is correct
9 Correct 44 ms 93276 KB Output is correct
10 Correct 26 ms 91484 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 91228 KB Output is correct
2 Correct 12 ms 91088 KB Output is correct
3 Correct 12 ms 91244 KB Output is correct
4 Correct 12 ms 91228 KB Output is correct
5 Correct 12 ms 91228 KB Output is correct
6 Correct 12 ms 91280 KB Output is correct
7 Correct 12 ms 91228 KB Output is correct
8 Correct 14 ms 91484 KB Output is correct
9 Correct 15 ms 91228 KB Output is correct
10 Correct 39 ms 93020 KB Output is correct
11 Incorrect 58 ms 94036 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 91228 KB Output is correct
2 Correct 12 ms 91088 KB Output is correct
3 Correct 12 ms 91244 KB Output is correct
4 Correct 12 ms 91228 KB Output is correct
5 Correct 12 ms 91228 KB Output is correct
6 Correct 12 ms 91280 KB Output is correct
7 Correct 12 ms 91228 KB Output is correct
8 Correct 14 ms 91484 KB Output is correct
9 Correct 15 ms 91228 KB Output is correct
10 Correct 39 ms 93020 KB Output is correct
11 Incorrect 58 ms 94036 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94292 KB Output is correct
2 Correct 11 ms 91380 KB Output is correct
3 Correct 12 ms 91084 KB Output is correct
4 Correct 12 ms 91228 KB Output is correct
5 Correct 12 ms 91128 KB Output is correct
6 Correct 12 ms 91224 KB Output is correct
7 Correct 12 ms 91228 KB Output is correct
8 Correct 44 ms 93104 KB Output is correct
9 Correct 44 ms 93276 KB Output is correct
10 Correct 26 ms 91484 KB Output is correct
11 Incorrect 63 ms 94284 KB Output isn't correct
12 Halted 0 ms 0 KB -