Submission #936716

#	Time	Username	Problem	Language	Result	Execution time	Memory
936716		browntoad	Price List (POI13_cen)	C++14	100 / 100	132 ms	20596 KiB

cen

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define endl '\n'

#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 1e5+5;
const ll inf = 1e18;
const ll mod = 1e9+7;

vector<int> G[maxn], G2[maxn];
vector<int> nxt[maxn]; // implement linked list
vector<int> adis(maxn);
vector<int> dis(maxn), tri(maxn);

int n, m, st, a, b;
signed main(){
    IOS();
    cin>>n>>m>>st>>a>>b;
    REP1(i, n){
        G2[i].pb(-1);
        nxt[i].pb(1);
    }
    REP(i, m){
        int u, v; cin>>u>>v;
        G[u].pb(v);
        G2[u].pb(v);
        nxt[u].pb(SZ(G2[u]));

        G[v].pb(u);
        G2[v].pb(u);
        nxt[v].pb(SZ(G2[v]));
    }
    REP1(i, n){
        G2[i].pb(-2);
    }

    fill(ALL(dis), -1);
    fill(ALL(adis), -1);

    int L = 0;
    vector<int> qu;
    qu.pb(st);
    adis[st] = 0;
    while(L < SZ(qu)){
        int u = qu[L++];
        for (auto v:G[u]){
            if (adis[v] == -1){
                adis[v] = adis[u]+1;
                qu.pb(v);
            }
        }
    }

    qu.pb(st);
    dis[st] = 0;
    while(L < SZ(qu)){
        int u = qu[L++];
        for(auto v:G[u]) tri[v] = 1;
        for(auto v:G[u]){
            int prev = 0, w;
            for (int i = nxt[v][0]; G2[v][i] != -2; i = nxt[v][i]){
                w = G2[v][i];
                if (dis[w] != -1) nxt[v][prev] = nxt[v][i];
                else if (!tri[w]){
                    dis[w] = dis[u]+1;
                    qu.pb(w);
                }
                else prev = i;
            }
        }
        for (auto v:G[u]) tri[v] = 0;
    }
    REP1(i, n){
        int ret = adis[i]/2*b;
        if (adis[i]%2){
            ret += a;
            if (dis[i] != -1) ret = min(ret, dis[i]*b); // only use b
        }
        ret = min(ret, adis[i]*a);// only use a
        cout<<ret<<endl;
    }
}
// number of triangles bounded by e sqrt(e)
/*
    algorithm for finding triangles in e sqrt(e): sort nodes by degree. add nodes into graph by decreasing degree number.
    when enumerating node u, only enumerate the edges from u -> v s.t. d(v) >= d(u). enumerate another k s.t. u->k and d(k) >= d(v).
    This is ok since the first enumeration is bounded by e and second enumeration bounded by sqrt(e) [proof by contradiction]

    use bitset to check? (or binary search???)
*/
/*
    whenever node u is ok: delete all v->u in G2 (don't need this)
    ensure everytime node edge G2 is run:
        u->v: v is visited: delete that edge: O(m) times
        u->v: v is marked as triangle: at most 6*esqrt(e) times
        u->v: v not visited -> visited: O(n) times
*/
/*
5 5 1 1000 1
1 2
2 3
2 4
4 3
3 5

4 4 1 1000 1
1 2
2 3
1 3
2 4

18 minutes?
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10