oj.uz

Submission #75163

# Submission time Handle Problem Language Result Execution time Memory
75163 2018-09-08T14:32:21 Z Kamisama Cities (BOI16_cities) C++14
74 / 100
 6000 ms 219580 KB 
#include <bits/stdc++.h>
#define up(i,a,b) for(int i=a;i<=b;i++)
#define down(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repd(i,a,b) for(int i=a-1;i>=b;i--)
#define CL(x) (x<<1)
#define CR(x) (x<<1)+1
#define pb push_back
#define bit1(x) __builtin_popcount(x)
#define self (*this)
#define Kamisama

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,pii> plii;
#define x first
#define y second

template<typename T> inline void _read(T &x){
    char ch; x=0; bool neg=false;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
        if(ch=='-') neg=true;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=10*x+ch-'0';
    if(neg) x=-x;
}
#define read(a) _read(a)
#define Read(a,b) _read(a),_read(b)
#define READ(a,b,c) _read(a),_read(b),_read(c)

const int maxn=1e5+7;
const int Nblocks=400;
const int maxS=(1<<5)+7;
const ll mod=9901;
const int inf=1e9+7;
const ll linf=1e16+9;
const double pi=4*atan(1);
const ll Radix=1e9;
const int Length=9;
const int MaxDigit=2e4+1;
const int nDigits=MaxDigit/Length+1;

/// Bit Manipulation
inline int SetBit(int x,int k){return x|(1<<k);}
inline bool IsSubSet(int x,int y){return (x&y)==0;}
/// End of Bit Manipulation

int n,m,k,city[maxn];
ll f[maxn][maxS];
vector<int> SubS[maxS];
vector<pli> a[maxn];
priority_queue< plii,vector<plii>,greater<plii> > q;

inline void Enter(){
    cin>>n>>k>>m;
    up(i,1,k){
        int p;
        cin>>p;
        city[p]=i;
    }
    up(i,1,m){
        int u,v,w;
        cin>>u>>v>>w;
        a[u].pb(pli(w,v));
        a[v].pb(pli(w,u));
    }
    //up(i,1,n) sort(a[i].begin(),a[i].end());
}

inline void Prepare(){
    int MaxState=(1<<k);
    rep(i,0,MaxState) rep(j,0,MaxState) if(IsSubSet(i,j)) SubS[i].pb(j);
    fill_n(&f[0][0],maxn*maxS,linf);
    up(i,1,n) if(city[i]) f[i][1<<(city[i]-1)]=0,q.push(plii(0,pii(i,1<<(city[i]-1))));

}

inline ll Dijkstra(){
    while(q.size()){
        ll w=q.top().x;
        auto u=q.top().y;
        q.pop();
        //cerr<<u<<' '<<State<<' '<<w<<'\n';
        if(w!=f[u.x][u.y]) continue;
        if(u.y==(1<<k)-1) return w;
        for(auto v: a[u.x]){
            ll Cost=w+v.x;
            int State=u.y;
            if(city[v.y]) State=SetBit(State,city[v.y]-1);
            if(f[v.y][State]>Cost){
                f[v.y][State]=Cost;
                q.push(plii(Cost,pii(v.y,State)));
            }
            for(int SubSet: SubS[State]){
                ll NewCost=Cost+f[v.y][SubSet];
                int NewState=State|SubSet;
                if(f[v.y][NewState]>NewCost){
                    f[v.y][NewState]=NewCost;
                    q.push(plii(NewCost,pii(v.y,NewState)));
                }
            }
        }
    }
    ll Res=linf;
    up(i,1,n) Res=min(Res,f[i][(1<<k)-1]);
    return Res;
}

inline void Solve(){
    cout<<Dijkstra();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    #ifndef Kamisama
    freopen("TEST.INP","r",stdin);
    freopen("TEST.OUT","w",stdout);
    #endif // Kamisama

    Enter();
    Prepare();
    Solve();

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 33272 KB Output is correct
2 Correct 27 ms 33408 KB Output is correct
3 Correct 28 ms 33408 KB Output is correct
4 Correct 27 ms 33568 KB Output is correct
5 Correct 26 ms 33572 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 64680 KB Output is correct
2 Correct 758 ms 68116 KB Output is correct
3 Correct 192 ms 68116 KB Output is correct
4 Correct 152 ms 68116 KB Output is correct
5 Correct 338 ms 68116 KB Output is correct
6 Correct 125 ms 68116 KB Output is correct
7 Correct 30 ms 68116 KB Output is correct
8 Correct 39 ms 68116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 68116 KB Output is correct
2 Correct 48 ms 68116 KB Output is correct
3 Correct 31 ms 68116 KB Output is correct
4 Correct 34 ms 68116 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2717 ms 136176 KB Output is correct
2 Correct 2277 ms 139496 KB Output is correct
3 Correct 1259 ms 139496 KB Output is correct
4 Correct 1699 ms 139496 KB Output is correct
5 Correct 369 ms 139496 KB Output is correct
6 Correct 247 ms 139496 KB Output is correct

Subtask #5
0 / 26.0

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