104852024-04-03 11:41:09Valaki2Autópálya inflációcpp17Hibás válasz 57/1002.009s23000 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 = 600;
const int mod = 1e9 + 7;
const 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 + 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
1Elfogadva8ms12420 KiB
2Hibás válasz1.786s16836 KiB
subtask28/8
3Elfogadva421ms13728 KiB
4Elfogadva300ms13740 KiB
5Elfogadva684ms14296 KiB
6Elfogadva888ms17148 KiB
7Elfogadva250ms13928 KiB
subtask315/15
8Elfogadva8ms13680 KiB
9Elfogadva9ms13792 KiB
10Elfogadva8ms13796 KiB
11Elfogadva9ms13836 KiB
12Elfogadva8ms13796 KiB
13Elfogadva8ms13924 KiB
14Elfogadva8ms14132 KiB
15Elfogadva8ms14080 KiB
16Elfogadva8ms14216 KiB
17Elfogadva7ms14212 KiB
18Elfogadva7ms14216 KiB
subtask434/34
19Elfogadva1.004s18384 KiB
20Elfogadva861ms15856 KiB
21Elfogadva883ms16652 KiB
22Elfogadva984ms16680 KiB
23Elfogadva967ms18292 KiB
24Elfogadva708ms15444 KiB
25Elfogadva1.031s18272 KiB
26Elfogadva1.072s18408 KiB
27Elfogadva546ms14972 KiB
28Elfogadva232ms15056 KiB
29Elfogadva217ms15300 KiB
30Elfogadva123ms15284 KiB
31Elfogadva238ms15356 KiB
32Elfogadva272ms15872 KiB
33Elfogadva270ms15848 KiB
subtask50/21
34Elfogadva583ms15528 KiB
35Elfogadva1.416s17020 KiB
36Elfogadva1.442s17020 KiB
37Elfogadva1.462s17244 KiB
38Elfogadva1.509s17264 KiB
39Elfogadva1.508s17196 KiB
40Elfogadva1.945s17172 KiB
41Időlimit túllépés2.009s17164 KiB
42Elfogadva241ms15480 KiB
43Elfogadva194ms15464 KiB
44Elfogadva194ms15504 KiB
45Elfogadva194ms15604 KiB
46Elfogadva230ms15380 KiB
47Elfogadva224ms15388 KiB
48Elfogadva310ms15596 KiB
49Elfogadva307ms15744 KiB
subtask60/22
50Hibás válasz1.24s16492 KiB
51Hibás válasz1.708s19328 KiB
52Elfogadva1.753s23000 KiB
53Hibás válasz1.789s22896 KiB
54Hibás válasz1.743s22868 KiB
55Hibás válasz1.741s22892 KiB
56Hibás válasz1.106s16064 KiB
57Hibás válasz1.11s16032 KiB
58Elfogadva143ms15788 KiB
59Elfogadva555ms16112 KiB
60Elfogadva531ms15988 KiB
61Elfogadva503ms15984 KiB
62Hibás válasz456ms15844 KiB
63Hibás válasz572ms16004 KiB
64Elfogadva689ms16356 KiB
65Elfogadva686ms16360 KiB
66Elfogadva564ms16184 KiB