oj.uz

Submission #936714

# Submission time Handle Problem Language Result Execution time Memory
936714 2024-03-02T15:20:05 Z browntoad Price List (POI13_cen) C++14
100 / 100
 106 ms 20836 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]%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 7 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8572 KB Output is correct

Subtask #2
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 3 ms 8540 KB Output is correct
4 Correct 2 ms 8540 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 2 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 9820 KB Output is correct
2 Correct 8 ms 9820 KB Output is correct
3 Correct 11 ms 10332 KB Output is correct
4 Correct 12 ms 10324 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13404 KB Output is correct
2 Correct 25 ms 13404 KB Output is correct
3 Correct 26 ms 12636 KB Output is correct
4 Correct 32 ms 14168 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16724 KB Output is correct
2 Correct 45 ms 15700 KB Output is correct
3 Correct 68 ms 18256 KB Output is correct
4 Correct 60 ms 18260 KB Output is correct
5 Correct 46 ms 17492 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 18516 KB Output is correct
2 Correct 50 ms 15964 KB Output is correct
3 Correct 68 ms 18776 KB Output is correct
4 Correct 61 ms 18256 KB Output is correct
5 Correct 54 ms 18624 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 20052 KB Output is correct
2 Correct 75 ms 18852 KB Output is correct
3 Correct 88 ms 19836 KB Output is correct
4 Correct 66 ms 18264 KB Output is correct
5 Correct 82 ms 19656 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 19212 KB Output is correct
2 Correct 85 ms 19284 KB Output is correct
3 Correct 100 ms 19836 KB Output is correct
4 Correct 63 ms 18260 KB Output is correct
5 Correct 74 ms 20424 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 19796 KB Output is correct
2 Correct 87 ms 19784 KB Output is correct
3 Correct 106 ms 20836 KB Output is correct
4 Correct 64 ms 18432 KB Output is correct
5 Correct 71 ms 20424 KB Output is correct