Submission #10,486

2024-04-03 11:43:53

cpp17

Time limit exceeded 78/100

2.099s

22684 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();
    }
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	8ms	11832 KiB
		2	Time limit exceeded	2.099s	8464 KiB
subtask2	8/8
		3	Accepted	483ms	13184 KiB
		4	Accepted	349ms	13112 KiB
		5	Accepted	813ms	13552 KiB
		6	Accepted	1.042s	16628 KiB
		7	Accepted	296ms	13536 KiB
subtask3	15/15
		8	Accepted	8ms	13404 KiB
		9	Accepted	9ms	13252 KiB
		10	Accepted	9ms	13516 KiB
		11	Accepted	9ms	13608 KiB
		12	Accepted	9ms	13600 KiB
		13	Accepted	8ms	13732 KiB
		14	Accepted	9ms	13972 KiB
		15	Accepted	8ms	13876 KiB
		16	Accepted	8ms	13892 KiB
		17	Accepted	8ms	13892 KiB
		18	Accepted	8ms	14020 KiB
subtask4	34/34
		19	Accepted	1.171s	18292 KiB
		20	Accepted	1.011s	16020 KiB
		21	Accepted	1.034s	17096 KiB
		22	Accepted	1.149s	16836 KiB
		23	Accepted	1.116s	18528 KiB
		24	Accepted	842ms	15752 KiB
		25	Accepted	1.19s	18644 KiB
		26	Accepted	1.238s	18644 KiB
		27	Accepted	676ms	15100 KiB
		28	Accepted	275ms	15008 KiB
		29	Accepted	256ms	14896 KiB
		30	Accepted	144ms	15140 KiB
		31	Accepted	280ms	15188 KiB
		32	Accepted	323ms	15356 KiB
		33	Accepted	321ms	15388 KiB
subtask5	21/21
		34	Accepted	538ms	15120 KiB
		35	Accepted	1.294s	16644 KiB
		36	Accepted	1.319s	16668 KiB
		37	Accepted	1.333s	16660 KiB
		38	Accepted	1.375s	16708 KiB
		39	Accepted	1.373s	16660 KiB
		40	Accepted	1.761s	16632 KiB
		41	Accepted	1.796s	16600 KiB
		42	Accepted	211ms	15004 KiB
		43	Accepted	173ms	14828 KiB
		44	Accepted	172ms	14828 KiB
		45	Accepted	172ms	14876 KiB
		46	Accepted	202ms	14904 KiB
		47	Accepted	197ms	15132 KiB
		48	Accepted	286ms	15280 KiB
		49	Accepted	284ms	15384 KiB
subtask6	0/22
		50	Wrong answer	1.496s	16392 KiB
		51	Time limit exceeded	2.016s	19252 KiB
		52	Time limit exceeded	2.059s	22684 KiB
		53	Time limit exceeded	2.073s	13260 KiB
		54	Time limit exceeded	2.046s	13100 KiB
		55	Time limit exceeded	2.043s	22652 KiB
		56	Wrong answer	1.393s	15788 KiB
		57	Wrong answer	1.396s	15732 KiB
		58	Accepted	177ms	15328 KiB
		59	Accepted	671ms	15748 KiB
		60	Accepted	644ms	15808 KiB
		61	Accepted	611ms	15776 KiB
		62	Wrong answer	555ms	15800 KiB
		63	Wrong answer	689ms	15692 KiB
		64	Accepted	837ms	16032 KiB
		65	Accepted	837ms	16056 KiB
		66	Accepted	694ms	15868 KiB