oj.uz

답안 #936719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
936719 2024-03-02T15:30:17 Z browntoad Price List (POI13_cen) C++14
100 / 100
 122 ms 19792 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]>>1)*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
 
*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8488 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 3 ms 8540 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9820 KB Output is correct
2 Correct 8 ms 9816 KB Output is correct
3 Correct 12 ms 10076 KB Output is correct
4 Correct 11 ms 10072 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 12892 KB Output is correct
2 Correct 23 ms 12920 KB Output is correct
3 Correct 33 ms 12236 KB Output is correct
4 Correct 33 ms 13652 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 15952 KB Output is correct
2 Correct 40 ms 14952 KB Output is correct
3 Correct 69 ms 17228 KB Output is correct
4 Correct 75 ms 17180 KB Output is correct
5 Correct 50 ms 16580 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 17492 KB Output is correct
2 Correct 59 ms 15244 KB Output is correct
3 Correct 73 ms 17744 KB Output is correct
4 Correct 67 ms 17232 KB Output is correct
5 Correct 59 ms 17608 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 19060 KB Output is correct
2 Correct 76 ms 18004 KB Output is correct
3 Correct 87 ms 18472 KB Output is correct
4 Correct 64 ms 17032 KB Output is correct
5 Correct 74 ms 18448 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 18192 KB Output is correct
2 Correct 80 ms 18256 KB Output is correct
3 Correct 122 ms 18768 KB Output is correct
4 Correct 65 ms 17232 KB Output is correct
5 Correct 95 ms 19376 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 18732 KB Output is correct
2 Correct 77 ms 18672 KB Output is correct
3 Correct 100 ms 19792 KB Output is correct
4 Correct 81 ms 17236 KB Output is correct
5 Correct 73 ms 19256 KB Output is correct