104862024-04-03 11:43:53Valaki2Autópálya inflációcpp17Időlimit túllépés 78/1002.099s22684 KiB
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC target ("avx2")
//#pragma GCC optimize("O3","unroll-loops")

#define distance distance1337

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

namespace bigmaxn {

const int maxn = 3100;
const int mod = 1e9 + 7;
int k = 32; // log2 max c_i + epsilon

struct distance {
    bitset<1 + maxn> bs;
    distance() {
        bs = 0;
    }
    distance(int num) {
        if(num == -1) {
            bs.set();
        } else {
            bs = num;
        }
    }
    distance(bitset<1 + maxn> bs_) {
        bs = bs_;
    }
    bool operator < (const distance &other) const {
        // reversed
        for(int i = maxn; i >= 0; i--) {
            if(other.bs[i] ^ bs[i]) {
                if(other.bs[i] > bs[i]) {
                    return false;
                } else {
                    return true;
                }
            }
        }
        return false;
    }
    // debug
    void print() {
        cout << bs.to_ullong();
    }
};

const distance inf = distance(-1);

int n, m;
vector<pii > graph[1 + maxn];
distance dist[1 + maxn][1 + 2];
bool done[1 + maxn][1 + 2];
int steps[1 + maxn];

void solve() {
    cin >> m;
    int maxci = 0;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
        maxci = max(maxci, c);
    }
    if(maxci <= 2) {
        k = 1;
    } else {
        k = 2;
    }
    queue<int> bfsq;
    bfsq.push(1);
    while(!bfsq.empty()) {
        int cur = bfsq.front();
        bfsq.pop();
        for(pii nei : graph[cur]) {
            if(nei.fi != 1 && steps[nei.fi] == 0) {
                bfsq.push(nei.fi);
                steps[nei.fi] = steps[cur] + 1;
            }
        }
    }
    priority_queue<pair<distance, pii > > q;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            dist[i][j] = distance(-1);
        }
    }
    dist[1][0].bs = 0;
    q.push(mp(dist[1][0], mp(1, 0)));
    while(!q.empty()) {
        pii curpair = q.top().se;
        q.pop();
        int cur = curpair.fi, cur_steps = curpair.se;
        int cur_idx = cur_steps - steps[cur];
        // cout << cur << " " << cur_steps << " " << cur_idx << ":\n";
        if(done[cur][cur_idx]) {
            continue;
        }
        done[cur][cur_idx] = true;
        if(cur_steps >= n) {
            continue;
        }
        for(pii nei : graph[cur]) {
            int nei_idx = cur_steps + 1 - steps[nei.fi];
            if(nei_idx > k) {
                continue;
            }
            bitset<1 + maxn> tmp = (bitset<1 + maxn>(nei.se) << cur_steps);
            int carry = 0;
            for(int i = 0; i <= maxn; i++) {
                int sum = dist[cur][cur_idx].bs[i] + tmp[i] + carry;
                carry = sum / 2;
                tmp[i] = sum % 2;
            }
            distance neidist = distance(tmp);
            // distance neidist = distance(dist[cur][cur_idx].bs + (bitset<1 + maxn>(nei.se) << cur_steps));
            // reversed
            if(dist[nei.fi][nei_idx] < neidist) {
                dist[nei.fi][nei_idx] = neidist;
                q.push(mp(neidist, mp(nei.fi, cur_steps + 1)));
            }
        }
    }
    /*for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            if(dist[i][j].bs[maxn] == 0) {
                dist[i][j].print();
            } else {
                cout << "-1";
            }
            cout << " ";
        }
        cout << "\n";
    }*/
    for(int i = 2; i <= n; i++) {
        distance ans_bs(-1);
        for(int j = 0; j <= k; j++) {
            ans_bs = max(ans_bs, dist[i][j]);
        }
        int ans = 0;
        int coeff = 1;
        for(int i = 0; i <= maxn; i++) {
            ans += coeff * ans_bs.bs[i];
            ans %= mod;
            coeff = (2 * coeff) % mod;
                    }
        cout << ans % mod << "\n";
    }
}

}

namespace smallmaxn {

const int maxn = 570;
const int mod = 1e9 + 7;
const int k = 31; // log2 max c_i + epsilon

struct distance {
    bitset<1 + maxn> bs;
    distance() {
        bs = 0;
    }
    distance(int num) {
        if(num == -1) {
            bs.set();
        } else {
            bs = num;
        }
    }
    distance(bitset<1 + maxn> bs_) {
        bs = bs_;
    }
    bool operator < (const distance &other) const {
        // reversed
        for(int i = maxn; i >= 0; i--) {
            if(other.bs[i] ^ bs[i]) {
                if(other.bs[i] > bs[i]) {
                    return false;
                } else {
                    return true;
                }
            }
        }
        return false;
    }
    // debug
    void print() {
        cout << bs.to_ullong();
    }
};

const distance inf = distance(-1);

int n, m;
vector<pii > graph[1 + maxn];
distance dist[1 + maxn][1 + k];
bool done[1 + maxn][1 + k];
int steps[1 + maxn];

void solve() {
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
    }
    queue<int> bfsq;
    bfsq.push(1);
    while(!bfsq.empty()) {
        int cur = bfsq.front();
        bfsq.pop();
        for(pii nei : graph[cur]) {
            if(nei.fi != 1 && steps[nei.fi] == 0) {
                bfsq.push(nei.fi);
                steps[nei.fi] = steps[cur] + 1;
            }
        }
    }
    priority_queue<pair<distance, pii > > q;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            dist[i][j] = distance(-1);
        }
    }
    dist[1][0].bs = 0;
    q.push(mp(dist[1][0], mp(1, 0)));
    while(!q.empty()) {
        pii curpair = q.top().se;
        q.pop();
        int cur = curpair.fi, cur_steps = curpair.se;
        int cur_idx = cur_steps - steps[cur];
        // cout << cur << " " << cur_steps << " " << cur_idx << ":\n";
        if(done[cur][cur_idx]) {
            continue;
        }
        done[cur][cur_idx] = true;
        if(cur_steps >= n) {
            continue;
        }
        for(pii nei : graph[cur]) {
            int nei_idx = cur_steps + 1 - steps[nei.fi];
            if(nei_idx > k) {
                continue;
            }
            bitset<1 + maxn> tmp = (bitset<1 + maxn>(nei.se) << cur_steps);
            int carry = 0;
            for(int i = 0; i <= maxn; i++) {
                int sum = dist[cur][cur_idx].bs[i] + tmp[i] + carry;
                carry = sum / 2;
                tmp[i] = sum % 2;
            }
            distance neidist = distance(tmp);
            // distance neidist = distance(dist[cur][cur_idx].bs + (bitset<1 + maxn>(nei.se) << cur_steps));
            // reversed
            if(dist[nei.fi][nei_idx] < neidist) {
                dist[nei.fi][nei_idx] = neidist;
                q.push(mp(neidist, mp(nei.fi, cur_steps + 1)));
            }
        }
    }
    /*for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= k; j++) {
            if(dist[i][j].bs[maxn] == 0) {
                dist[i][j].print();
            } else {
                cout << "-1";
            }
            cout << " ";
        }
        cout << "\n";
    }*/
    for(int i = 2; i <= n; i++) {
        distance ans_bs(-1);
        for(int j = 0; j <= k; j++) {
            ans_bs = max(ans_bs, dist[i][j]);
        }
        int ans = 0;
        int coeff = 1;
        for(int i = 0; i <= maxn; i++) {
            ans += coeff * ans_bs.bs[i];
            ans %= mod;
            coeff = (2 * coeff) % mod;
                    }
        cout << ans % mod << "\n";
    }
}

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    if(n <= 500) {
        smallmaxn::n = n;
        smallmaxn::solve();
    } else {
        bigmaxn::n = n;
        bigmaxn::solve();
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva8ms11832 KiB
2Időlimit túllépés2.099s8464 KiB
subtask28/8
3Elfogadva483ms13184 KiB
4Elfogadva349ms13112 KiB
5Elfogadva813ms13552 KiB
6Elfogadva1.042s16628 KiB
7Elfogadva296ms13536 KiB
subtask315/15
8Elfogadva8ms13404 KiB
9Elfogadva9ms13252 KiB
10Elfogadva9ms13516 KiB
11Elfogadva9ms13608 KiB
12Elfogadva9ms13600 KiB
13Elfogadva8ms13732 KiB
14Elfogadva9ms13972 KiB
15Elfogadva8ms13876 KiB
16Elfogadva8ms13892 KiB
17Elfogadva8ms13892 KiB
18Elfogadva8ms14020 KiB
subtask434/34
19Elfogadva1.171s18292 KiB
20Elfogadva1.011s16020 KiB
21Elfogadva1.034s17096 KiB
22Elfogadva1.149s16836 KiB
23Elfogadva1.116s18528 KiB
24Elfogadva842ms15752 KiB
25Elfogadva1.19s18644 KiB
26Elfogadva1.238s18644 KiB
27Elfogadva676ms15100 KiB
28Elfogadva275ms15008 KiB
29Elfogadva256ms14896 KiB
30Elfogadva144ms15140 KiB
31Elfogadva280ms15188 KiB
32Elfogadva323ms15356 KiB
33Elfogadva321ms15388 KiB
subtask521/21
34Elfogadva538ms15120 KiB
35Elfogadva1.294s16644 KiB
36Elfogadva1.319s16668 KiB
37Elfogadva1.333s16660 KiB
38Elfogadva1.375s16708 KiB
39Elfogadva1.373s16660 KiB
40Elfogadva1.761s16632 KiB
41Elfogadva1.796s16600 KiB
42Elfogadva211ms15004 KiB
43Elfogadva173ms14828 KiB
44Elfogadva172ms14828 KiB
45Elfogadva172ms14876 KiB
46Elfogadva202ms14904 KiB
47Elfogadva197ms15132 KiB
48Elfogadva286ms15280 KiB
49Elfogadva284ms15384 KiB
subtask60/22
50Hibás válasz1.496s16392 KiB
51Időlimit túllépés2.016s19252 KiB
52Időlimit túllépés2.059s22684 KiB
53Időlimit túllépés2.073s13260 KiB
54Időlimit túllépés2.046s13100 KiB
55Időlimit túllépés2.043s22652 KiB
56Hibás válasz1.393s15788 KiB
57Hibás válasz1.396s15732 KiB
58Elfogadva177ms15328 KiB
59Elfogadva671ms15748 KiB
60Elfogadva644ms15808 KiB
61Elfogadva611ms15776 KiB
62Hibás válasz555ms15800 KiB
63Hibás válasz689ms15692 KiB
64Elfogadva837ms16032 KiB
65Elfogadva837ms16056 KiB
66Elfogadva694ms15868 KiB