Submission #53141793

Source Code Expand

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

#include <algorithm>
#include <atcoder/all>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using namespace atcoder;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define repk(i, k, n) for (int i = k; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define mod1 1000000007
#define mod2 998244353
#define mod3 100000007
#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vvl vector<vector<ll>>
#define vvb vector<vector<bool>>
#define vvvi vector<vector<vector<int>>>
#define vvvl vector<vector<vector<ll>>>
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define vvpii vector<vector<pair<int, int>>>
#define vvpll vector<vector<pair<ll, ll>>>

using mint = modint998244353;

template <typename T>
void debug(T e) {
    cerr << e << endl;
}

template <typename T>
void debug(vector<T> &v) {
    rep(i, v.size()) { cerr << v[i] << " "; }
    cerr << endl;
}

template <typename T>
void debug(vector<vector<T>> &v) {
    rep(i, v.size()) {
        rep(j, v[i].size()) { cerr << v[i][j] << " "; }
        cerr << endl;
    }
}

template <typename T>
void debug(vector<pair<T, T>> &v) {
    rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; }
}

template <typename T>
void debug(set<T> &st) {
    for (auto itr = st.begin(); itr != st.end(); itr++) {
        cerr << *itr << " ";
    }
    cerr << endl;
}

template <typename T>
void debug(multiset<T> &ms) {
    for (auto itr = ms.begin(); itr != ms.end(); itr++) {
        cerr << *itr << " ";
    }
    cerr << endl;
}

template <typename T>
void debug(map<T, T> &mp) {
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        cerr << itr->first << " " << itr->second << endl;
    }
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << H << " ";
    debug_out(T...);
}

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M);
    vector<ll> B(M);
    vector<ll> C(M);
    for (ll i = 0; i < M; i++) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--;
        B[i]--;
    }
    for (ll i = 0; i < M; i++) {
        if (A[i] > B[i]) {
            swap(A[i], B[i]);
            C[i] *= -1;
        }
    }
    vector<vector<pll>> graph(N, vector<pll>(0));
    for (ll i = 0; i < M; i++) {
        graph[A[i]].push_back(pll(B[i], -C[i]));
        graph[B[i]].push_back(pll(A[i], C[i]));
    }
    vector<vector<ll>> vecs(0, vector<ll>(0));
    vector<vector<ll>> places(0, vector<ll>(0));
    vector<bool> isvisited(N, false);
    vector<ll> height(N, 0);
    for (ll i = 0; i < N; i++) {
        vector<pll> subs(0);
        vector<ll> sub_places(0);
        if (isvisited[i]) {
            continue;
        }
        isvisited[i] = true;
        queue<ll> que;
        que.push(i);
        subs.push_back(pll(height[i], i));
        while (que.size()) {
            ll p = que.front();
            que.pop();
            for (pll v : graph[p]) {
                if (isvisited[v.first]) {
                    continue;
                }
                isvisited[v.first] = true;
                height[v.first] = height[p] + v.second;
                que.push(v.first);
                subs.push_back(pll(height[v.first], v.first));
            }
        }
        sort(all(subs));
        ll hval = -subs[0].first;
        for (ll j = 0; j < subs.size(); j++) {
            subs[j].first += hval;
        }
        vector<ll> sub_vecs(0);
        vector<ll> sub_place(0);
        for (ll j = 0; j < subs.size(); j++) {
            sub_vecs.push_back(subs[j].first);
            sub_places.push_back(subs[j].second);
        }
        vecs.push_back(sub_vecs);
        places.push_back(sub_places);
    }
    // debug(vecs);
    // debug(places);
    ll len = vecs.size();
    // 置き方を bit DP により確かめる
    vector<vector<bool>> bitdp(len + 1, vector<bool>(1 << N, false));
    bitdp[0][0] = true;
    for (ll i = 0; i < len; i++) {
        for (ll j = 0; j < (1 << N); j++) {
            if (!bitdp[i][j]) {
                continue;
            }
            for (ll k = 0; k < N - vecs[i][vecs[i].size() - 1]; k++) {
                bool pos = true;
                for (ll l = 0; l < vecs[i].size(); l++) {
                    if ((j >> (vecs[i][l] + k)) & 1) {
                        pos = false;
                    }
                }
                if (pos) {
                    ll new_bits = 0;
                    for (ll l = 0; l < vecs[i].size(); l++) {
                        new_bits += (1 << (vecs[i][l] + k));
                    }
                    bitdp[i + 1][j | new_bits] = true;
                }
            }
        }
    }
    vector<vector<bool>> part_pos(N, vector<bool>(N, false));
    vector<vector<bool>> pos_bitdp(len + 1, vector<bool>(1 << N, false));
    for (ll j = 0; j < (1 << N); j++) {
        if (bitdp[len][j]) pos_bitdp[len][j] = true;
    }
    // dp の復元により可能性を確かめる
    for (ll i = len; i > 0; i--) {
        for (ll j = 0; j < (1 << N); j++) {
            if (!pos_bitdp[i][j]) {
                continue;
            }
            for (ll k = 0; k < N - vecs[i - 1][vecs[i - 1].size() - 1]; k++) {
                bool pos = true;
                for (ll l = 0; l < vecs[i - 1].size(); l++) {
                    if (!((j >> (vecs[i - 1][l] + k)) & 1)) {
                        pos = false;
                    }
                }
                if (pos) {
                    ll new_bits = 0;
                    for (ll l = 0; l < vecs[i - 1].size(); l++) {
                        new_bits += (1 << (vecs[i - 1][l] + k));
                    }
                    if (bitdp[i - 1][j - new_bits]) {
                        pos_bitdp[i - 1][j - new_bits] = true;
                        for (ll l = 0; l < vecs[i - 1].size(); l++) {
                            part_pos[places[i - 1][l]][vecs[i - 1][l] + k] =
                                true;
                        }
                    }
                }
            }
        }
    }
    // debug(pos_bitdp);
    // debug(part_pos);
    vector<ll> ans(N, -1);
    vector<ll> cnts(N, 0);
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            if (part_pos[i][j]) {
                ans[i] = j;
                cnts[i]++;
            }
        }
    }
    for (ll i = 0; i < N; i++) {
        if (cnts[i] >= 2) {
            cout << -1 << " ";
        } else {
            cout << ans[i] + 1 << " ";
        }
    }
    cout << endl;
}

Submission Info

Submission Time
Task F - Estimate Order
User AngrySadEight
Language C++ 20 (gcc 12.2)
Score 525
Code Size 7501 Byte
Status AC
Exec Time 15 ms
Memory 3920 KiB

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:163:26: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  163 |         for (ll j = 0; j < subs.size(); j++) {
      |                        ~~^~~~~~~~~~~~~
Main.cpp:168:26: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<std::pair<long long int, long long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  168 |         for (ll j = 0; j < subs.size(); j++) {
      |                        ~~^~~~~~~~~~~~~
Main.cpp:188:34: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  188 |                 for (ll l = 0; l < vecs[i].size(); l++) {
      |                                ~~^~~~~~~~~~~~~~~~
Main.cpp:195:38: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  195 |                     for (ll l = 0; l < vecs[i].size(); l++) {
      |                                    ~~^~~~~~~~~~~~~~~~
Main.cpp:216:34: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  216 |                 for (ll l = 0; l < vecs[i - 1].size(); l++) {
      |                                ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:223:38: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  223 |                     for (ll l = 0; l < vecs[i - 1].size(); l++) {
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:228:42: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  228 |                         for (ll l = 0; l < vecs[i - 1].size(); l++) {
      |                                        ~~^~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 525 / 525
Status
AC × 3
AC × 62
Set Name Test Cases
Sample sample00.txt, sample01.txt, sample02.txt
All sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt, testcase35.txt, testcase36.txt, testcase37.txt, testcase38.txt, testcase39.txt, testcase40.txt, testcase41.txt, testcase42.txt, testcase43.txt, testcase44.txt, testcase45.txt, testcase46.txt, testcase47.txt, testcase48.txt, testcase49.txt, testcase50.txt, testcase51.txt, testcase52.txt, testcase53.txt, testcase54.txt, testcase55.txt, testcase56.txt, testcase57.txt, testcase58.txt
Case Name Status Exec Time Memory
sample00.txt AC 1 ms 3604 KiB
sample01.txt AC 1 ms 3584 KiB
sample02.txt AC 1 ms 3644 KiB
testcase00.txt AC 1 ms 3700 KiB
testcase01.txt AC 1 ms 3668 KiB
testcase02.txt AC 1 ms 3648 KiB
testcase03.txt AC 1 ms 3788 KiB
testcase04.txt AC 1 ms 3716 KiB
testcase05.txt AC 1 ms 3684 KiB
testcase06.txt AC 1 ms 3660 KiB
testcase07.txt AC 1 ms 3628 KiB
testcase08.txt AC 1 ms 3732 KiB
testcase09.txt AC 1 ms 3740 KiB
testcase10.txt AC 1 ms 3744 KiB
testcase11.txt AC 1 ms 3880 KiB
testcase12.txt AC 1 ms 3676 KiB
testcase13.txt AC 1 ms 3872 KiB
testcase14.txt AC 1 ms 3692 KiB
testcase15.txt AC 1 ms 3776 KiB
testcase16.txt AC 2 ms 3780 KiB
testcase17.txt AC 2 ms 3908 KiB
testcase18.txt AC 2 ms 3856 KiB
testcase19.txt AC 2 ms 3716 KiB
testcase20.txt AC 1 ms 3732 KiB
testcase21.txt AC 2 ms 3728 KiB
testcase22.txt AC 2 ms 3728 KiB
testcase23.txt AC 2 ms 3920 KiB
testcase24.txt AC 2 ms 3784 KiB
testcase25.txt AC 2 ms 3708 KiB
testcase26.txt AC 2 ms 3704 KiB
testcase27.txt AC 5 ms 3724 KiB
testcase28.txt AC 3 ms 3856 KiB
testcase29.txt AC 3 ms 3784 KiB
testcase30.txt AC 5 ms 3876 KiB
testcase31.txt AC 4 ms 3896 KiB
testcase32.txt AC 5 ms 3780 KiB
testcase33.txt AC 7 ms 3724 KiB
testcase34.txt AC 8 ms 3724 KiB
testcase35.txt AC 7 ms 3772 KiB
testcase36.txt AC 11 ms 3632 KiB
testcase37.txt AC 10 ms 3780 KiB
testcase38.txt AC 12 ms 3736 KiB
testcase39.txt AC 5 ms 3860 KiB
testcase40.txt AC 11 ms 3788 KiB
testcase41.txt AC 10 ms 3720 KiB
testcase42.txt AC 13 ms 3916 KiB
testcase43.txt AC 15 ms 3728 KiB
testcase44.txt AC 13 ms 3724 KiB
testcase45.txt AC 15 ms 3708 KiB
testcase46.txt AC 15 ms 3636 KiB
testcase47.txt AC 15 ms 3900 KiB
testcase48.txt AC 4 ms 3804 KiB
testcase49.txt AC 2 ms 3588 KiB
testcase50.txt AC 8 ms 3920 KiB
testcase51.txt AC 1 ms 3628 KiB
testcase52.txt AC 1 ms 3624 KiB
testcase53.txt AC 1 ms 3656 KiB
testcase54.txt AC 1 ms 3664 KiB
testcase55.txt AC 1 ms 3600 KiB
testcase56.txt AC 1 ms 3652 KiB
testcase57.txt AC 1 ms 3620 KiB
testcase58.txt AC 1 ms 3604 KiB