oj.uz

Submission #1083079

# Submission time Handle Problem Language Result Execution time Memory
1083079 2024-09-02T12:55:05 Z User0069 Cities (BOI16_cities) C++17
74 / 100
 6000 ms 178320 KB 
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int long long
using namespace std;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
const int maxn=1e5+33;
const int N=1e5;
const int mod=1e9+7;
const long long INF=1e18;
int n,k,m,imp[maxn],vis[maxn][32];
long long dp[maxn][32];
vector<int> adj[maxn];
struct edge
{
    int u,v,w;
}e[2*maxn];
struct ele
{
    int des,mask;
    long long dis;
};
bool operator <(ele a,ele b)
{
    return a.dis>b.dis;
}
priority_queue<ele> pq;
void predijkstra()
{
    for(int i=1;i<=n;i++)
    {
        if(imp[i])
        {
            pq.push({i,1<<(imp[i]-1),0});
        }
    }
    while(!pq.empty())
    {
        int des=pq.top().des;
        long long dis=pq.top().dis;
        int mask=pq.top().mask;
        pq.pop();
        if(vis[des][mask]) continue;
        dp[des][mask]=dis;
        vis[des][mask]=1;
        for(int i:adj[des])
        {
            int des1=e[i].u+e[i].v-des;
            if(!vis[des1][mask])
            pq.push({des1,mask,dis+e[i].w});
        }
    }
}
long long dijkstra()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(1<<k);j++) vis[i][j]=0;
        if(imp[i])
        {
            pq.push({i,0,0});
        }
    }
    while(!pq.empty())
    {
        int des=pq.top().des;
        long long dis=pq.top().dis;
        int mask=pq.top().mask;
        pq.pop();
        if(mask==(1<<k)-1) return dis;
        if(vis[des][mask]) continue;
        dp[des][mask]=dis;
        vis[des][mask]=1;
        for(int i:adj[des])
        {
            int des1=e[i].u+e[i].v-des;
            if(!vis[des1][mask])
            pq.push({des1,mask,dis+e[i].w});
        }
        for(int i=0;i<k;i++)
        {
            if(((1<<i)|mask)!=mask)
            {
                if(!vis[des][mask^(1<<i)])
                {
                    pq.push({des,(1<<i)^mask,dp[des][mask]+dp[des][1<<i]});
                }
            }
        }
    }
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n>>k>>m;
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        imp[x]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].u>>e[i].v>>e[i].w;
        adj[e[i].u].push_back(i);
        adj[e[i].v].push_back(i);
    }
    predijkstra();
    cout<<dijkstra();
//    long long ans=INF;
//    for(int i=1;i<=n;i++)
//    {
//        if(vis[i][(1<<k)-1]) ans=min(ans,dp[i][(1<<k)-1]);
////        for(int j=0;j<k;j++)
////        {
////            cout<<f[i][j]<<" ";
////        }
////        cout<<"\n";
//    }
//    cout<<ans;
}

Compilation message

cities.cpp: In function 'long long int dijkstra()':
cities.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
   95 | }
      | ^
cities.cpp: In function 'int main()':
cities.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 63476 KB Output is correct
2 Correct 851 ms 63152 KB Output is correct
3 Correct 150 ms 48836 KB Output is correct
4 Correct 240 ms 40656 KB Output is correct
5 Correct 335 ms 55220 KB Output is correct
6 Correct 115 ms 16080 KB Output is correct
7 Correct 4 ms 3672 KB Output is correct
8 Correct 3 ms 3420 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3800 KB Output is correct
2 Correct 8 ms 3800 KB Output is correct
3 Correct 5 ms 3584 KB Output is correct
4 Correct 7 ms 3544 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3045 ms 112696 KB Output is correct
2 Correct 2643 ms 112264 KB Output is correct
3 Correct 1241 ms 77648 KB Output is correct
4 Correct 1828 ms 60316 KB Output is correct
5 Correct 601 ms 77192 KB Output is correct
6 Correct 386 ms 74368 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6072 ms 178320 KB Time limit exceeded
2 Halted 0 ms 0 KB -