oj.uz

Submission #936716

# Submission time Handle Problem Language Result Execution time Memory
936716 2024-03-02T15:28:31 Z browntoad Price List (POI13_cen) C++14
100 / 100
 132 ms 20596 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8664 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8500 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10076 KB Output is correct
2 Correct 9 ms 10076 KB Output is correct
3 Correct 12 ms 10328 KB Output is correct
4 Correct 11 ms 10332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13272 KB Output is correct
2 Correct 22 ms 13272 KB Output is correct
3 Correct 25 ms 12516 KB Output is correct
4 Correct 38 ms 14020 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16588 KB Output is correct
2 Correct 47 ms 15624 KB Output is correct
3 Correct 80 ms 17992 KB Output is correct
4 Correct 80 ms 17808 KB Output is correct
5 Correct 52 ms 17344 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 18124 KB Output is correct
2 Correct 43 ms 15840 KB Output is correct
3 Correct 70 ms 18588 KB Output is correct
4 Correct 69 ms 17868 KB Output is correct
5 Correct 57 ms 18312 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19876 KB Output is correct
2 Correct 79 ms 18692 KB Output is correct
3 Correct 132 ms 19064 KB Output is correct
4 Correct 70 ms 17868 KB Output is correct
5 Correct 66 ms 19432 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 19180 KB Output is correct
2 Correct 74 ms 19180 KB Output is correct
3 Correct 118 ms 19624 KB Output is correct
4 Correct 66 ms 17980 KB Output is correct
5 Correct 73 ms 20028 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 19652 KB Output is correct
2 Correct 80 ms 19488 KB Output is correct
3 Correct 124 ms 20596 KB Output is correct
4 Correct 79 ms 17924 KB Output is correct
5 Correct 73 ms 20160 KB Output is correct