oj.uz

Submission #936721

# Submission time Handle Problem Language Result Execution time Memory
936721 2024-03-02T15:32:23 Z browntoad Price List (POI13_cen) C++14
100 / 100
 112 ms 19684 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);
    queue<int> qu;
    qu.push(st);
    adis[st] = 0;
    while(SZ(qu)){
        int u = qu.front(); qu.pop();
        for (auto v:G[u]){
            if (adis[v] == -1){
                adis[v] = adis[u]+1;
                qu.push(v);
            }
        }
    }
 
    qu.push(st);
    dis[st] = 0;
    while(SZ(qu)){
        int u = qu.front(); qu.pop();
        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.push(w);
                }
                else prev = i;
            }
        }
        for (auto v:G[u]) tri[v] = 0;
    }
    REP1(i, n){
        int ret = adis[i]/2*b;
        if (adis[i]&1){
            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 8496 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 3 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8496 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 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 8540 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9816 KB Output is correct
2 Correct 10 ms 10072 KB Output is correct
3 Correct 12 ms 10076 KB Output is correct
4 Correct 11 ms 10076 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12760 KB Output is correct
2 Correct 23 ms 12924 KB Output is correct
3 Correct 24 ms 12212 KB Output is correct
4 Correct 34 ms 13660 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16028 KB Output is correct
2 Correct 38 ms 14856 KB Output is correct
3 Correct 62 ms 17228 KB Output is correct
4 Correct 91 ms 17232 KB Output is correct
5 Correct 50 ms 16580 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 17328 KB Output is correct
2 Correct 43 ms 15196 KB Output is correct
3 Correct 112 ms 17632 KB Output is correct
4 Correct 70 ms 17232 KB Output is correct
5 Correct 62 ms 17604 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 19024 KB Output is correct
2 Correct 67 ms 17820 KB Output is correct
3 Correct 76 ms 18384 KB Output is correct
4 Correct 64 ms 17036 KB Output is correct
5 Correct 81 ms 18628 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 18260 KB Output is correct
2 Correct 76 ms 18196 KB Output is correct
3 Correct 79 ms 18772 KB Output is correct
4 Correct 90 ms 17240 KB Output is correct
5 Correct 88 ms 19396 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 18772 KB Output is correct
2 Correct 91 ms 18592 KB Output is correct
3 Correct 99 ms 19684 KB Output is correct
4 Correct 68 ms 17192 KB Output is correct
5 Correct 77 ms 19396 KB Output is correct