oj.uz

Submission #559937

# Submission time Handle Problem Language Result Execution time Memory
559937 2022-05-11T01:21:40 Z Huy Cities (BOI16_cities) C++17
0 / 100
 223 ms 38260 KB 
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = (int)5e5;
const int maxN = (int)5e5 + 5;
const ll mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e17;
const ll logn = 18;
const int base = 311;
const int Block_size = 500;
const int ep = 'a';

int cu[] = {0,0,1,-1};
int cv[] = {-1,1,0,0};

int du[] = {-1,-1,+1,1};
int dv[] = {-1,+1,-1,1};

int cled[] = {6,2,5,5,4,5,6,3,7,6};

void InputFile()
{
    freopen(".inp","r",stdin);
    freopen(".out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,k,m;
int spec[maxN];
vector<vector<pii>> adj;

void Read()
{
   cin >> n >> k >> m;
   adj.resize(n+1);
   for(int i = 1;i <= k;i++)
   {
       cin >> spec[i];
       spec[i]--;
   }
   for(int i = 1;i <= m;i++)
   {
       int x,y,w;
       cin >> x >> y >> w;
       x--;
       y--;
       adj[x].push_back({y,w});
       adj[y].push_back({x,w});
   }
}

int dp[(1 << 5)][maxN];

void Solve()
{
    /// init
    for(int i = 0;i < n;i++)
    {
        for(int mask = 0;mask < (1 << k);mask++)
        {
            dp[mask][i] = infty;
            if(mask == 0) dp[mask][i] = 0;
        }
    }
    for(int i = 1;i <= k;i++)
    {
        dp[(1<<(i-1))][spec[i]] = 0;
        dp[0][spec[i]] = infty;
    }

    ///
    for(int mask = 1;mask < (1 << k);mask++)
    {
        for(int i = 0;i < n;i++)
        {
            for(int pre_mask1 = 1;pre_mask1 < (1 << k);pre_mask1++)
            {
                if((mask & pre_mask1) == pre_mask1)
                {
                    int pre_mask2 = mask ^ pre_mask1;
                    dp[mask][i] = min(dp[mask][i],dp[pre_mask1][i] + dp[pre_mask2][i]);
                }
            }
        }
    }

    int res = infty;
    for(int i = 0;i < n;i++)
    {
        res = min(res,dp[(1<<k)-1][i]);
    }
    cout << res;
}

void Debug()
{
    //Main_sub();
    //Naive();
}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message

cities.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
cities.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      | 
cities.cpp: In function 'void InputFile()':
cities.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen(".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
cities.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen(".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 22.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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