QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291934#7118. Closing TimeHaccerKat0 188ms74136kbC++208.2kb2023-12-27 14:04:092024-04-28 08:00:42

Judging History

你现在查看的是最新测评结果

  • [2024-04-28 08:00:42]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:188ms
  • 内存:74136kb
  • [2023-12-27 14:04:10]
  • 评测
  • 测评结果:0
  • 用时:130ms
  • 内存:74156kb
  • [2023-12-27 14:04:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

// #define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

// #define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);
#define dbgm(...)

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
template <class T>
class pointsegtree {
public:
    int n;
    T inf = 2e18;
    vector<T> t;
    vector<int> cnt;
    pointsegtree(int n) {
        this->n = n;
        t.resize(n * 4);
        cnt.resize(n * 4);
    }
    
    void update(int p, T x, int c, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = x, cnt[v] = c;
            return;
        }
        
        int mid = (tl + tr) / 2;
        if (p <= mid) update(p, x, c, v * 2, tl, mid);
        else update(p, x, c, v * 2 + 1, mid + 1, tr);
        t[v] = t[v * 2] + t[v * 2 + 1];
        t[v] = min(t[v], inf);
        cnt[v] = cnt[v * 2] + cnt[v * 2 + 1];
    }
    
    void update(int p, T x, int c) {
        update(p, x, c, 1, 0, n - 1);
    }
    
    int query(T c, int v, int tl, int tr) {
        if (tl == tr) return t[v] > c ? 0 : cnt[v];
        int mid = (tl + tr) / 2;
        if (t[v * 2] >= c) return query(c, v * 2, tl, mid);
        else return cnt[v * 2] + query(c - t[v * 2], v * 2 + 1, mid + 1, tr);
    }
    
    int query(T c) {
        return query(c, 1, 0, n - 1);
    }
};

const ll inf = 2e18;
void dfs(int u, vector<vector<pi>> &adj, vector<ll> &d, vector<int> &p) {
    for (auto [v, w] : adj[u]) {
        if (v != p[u]) {
            d[v] = d[u] + w, p[v] = u;
            dfs(v, adj, d, p);
        }
    }
}

int slv(int n, vector<ll> &aa, vector<ll> &bb, ll k) {
    vector<pll> a(n);
    vector<vector<int>> b(n, vector<int>(2));
    // dbg(aa);
    // dbg(bb);
    for (int i = 0; i < n; i++) {
        a[i] = {bb[i], aa[i]};
    }
    
    sort(a.begin(), a.end());
    // dbg(a);
    vector<pair<ll, pi>> vals(2 * n);
    for (int i = 0; i < n; i++) {
        auto [y, x] = a[i];
        vals[i * 2] = {x, {i, 0}};
        vals[i * 2 + 1] = {y - x, {i, 1}};
    }
    
    sort(vals.begin(), vals.end());
    pointsegtree<ll> st(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        auto [v, pa] = vals[i];
        auto [p, t] = pa;
        if (!t) {
            dbgm(v, p, t);
            st.update(i, v, 1);
        }
         
        b[p][t] = i;
    }
    
    // dbg(b);
    int out = 0;
    for (int i = 0; i <= n; i++) {
        if (k < 0) break;
        out = max(out, i + st.query(k));
        auto [y, x] = a[i];
        dbgm(out, k, i, st.query(k));
        k -= x;
        if (i == n) break;
        st.update(b[i][0], 0, 0);
        st.update(b[i][1], y - x, 1);
    }
    
    return out;
}

int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
    vector<vector<pi>> adj(n);
    vector<ll> dx(n, inf), dy(n, inf), a(n), b(n);
    vector<int> px(n), py(n);
    for (int i = 0; i < n - 1; i++) {
        adj[u[i]].push_back({v[i], w[i]});
        adj[v[i]].push_back({u[i], w[i]});
    }
    
    dx[x] = dy[y] = 0, px[x] = py[y] = -1;
    dfs(x, adj, dx, px);
    dfs(y, adj, dy, py);
    int out = 0;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        a[i] = min(dx[i], dy[i]), b[i] = max(dx[i], dy[i]);
        c[i] = a[i];
    }
    
    sort(c.begin(), c.end());
    ll cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur + c[i] > k) break;
        cur += c[i], out++;
    }
    
    // dbg(dx);
    // dbg(dy);
    // dbg(px);
    // dbg(py);
    // dbg(out);
    if (cur > k) return out;
    cur = 0;
    int uu = y, cnt = 0;
    while (true) {
        cur += a[uu], cnt++;
        b[uu] -= a[uu];
        swap(b[uu], a[uu]);
        b[uu] = inf;
        if (uu == x) break;
        uu = px[uu];
    }
    
    k -= cur;
    return max(out, cnt + slv(n, a, b, k));
}

// void solve() {
// // •   DO NOT GET STUCK ON ONE APPROACH!
// // •   Refusing to switch problems is the sign of tunnel vison
// // •   REREAD!
// // •   REMEMBER THAT ALL THAT MATTERS IS THE TOTAL SCORE!
// // •   GET SUBTASKS!
// // •   Plan the rest of the contest out!
// // •   Look at the constraints
// // •   Look for edge cases like n = 1
// // •   Set bounds of stress tests randomly
// // •   Think more, mindlessly debug less
// // •   Graphs can be disconnected
// // •   Integer overflow
// // •   READ the SAMPLES!
// // When stuck on ideas:
// // •   DFS trees
//     // int out = max_score(7, 0, 2, 10, {0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3});
//     // int out = max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19});
//     int out = max_score(8, 0, 1, 14, {0, 0, 0, 0, 1, 1, 1}, {1, 2, 3, 4, 5, 6, 7}, {1, 4, 3, 5, 5, 1, 2});
//     cout << out << "\n";
// }

// int32_t main() {
//     std::ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     solve();
// }

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 188ms
memory: 74136kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
200000 31011 61157 8517583098
31011 129396 964383
1655 129396 331139
1655 191487 566483
110385 191487 865248
43212 110385 542661
43212 81682 13766
81682 91774 546589
91774 124706 780638
124706 175650 118706
10421 175650 615314
10421 151953 436270
140430 151...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
200000

result:

wrong answer 1st lines differ - on the 1st token, expected: '451', found: '200000'

Subtask #2:

score: 0
Wrong Answer

Test #4:

score: 9
Accepted
time: 1ms
memory: 3840kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
50 23 25 382806473
0 1 375710
1 2 898637
2 3 10402
3 4 536577
4 5 385023
5 6 71075
6 7 543368
7 8 301497
8 9 174394
9 10 711312
10 11 923006
11 12 675532
12 13 838667
13 14 565729
14 15 979816
15 16 862618
16 17 576015
17 18 177751
18 19 306989
19 20 881492...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
96

result:

ok 

Test #5:

score: 0
Accepted
time: 1ms
memory: 4136kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
47 20 22 25669694
0 1 291237
1 2 851987
2 3 421247
3 4 962919
4 5 643085
5 6 224951
6 7 756890
7 8 147295
8 9 625823
9 10 736374
10 11 290526
11 12 335466
12 13 539086
13 14 957449
14 15 423408
15 16 932444
16 17 356032
17 18 307118
18 19 94279
19 20 989546...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
26

result:

ok 

Test #6:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
46 6 34 355277954
0 1 574359
1 2 58362
2 3 778155
3 4 538832
4 5 128903
5 6 79774
6 7 715282
7 8 259924
8 9 640303
9 10 361135
10 11 506866
11 12 527045
12 13 946672
13 14 620381
14 15 701743
15 16 766266
16 17 524732
17 18 340089
18 19 630172
19 20 357712
...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
74

result:

ok 

Test #7:

score: -9
Wrong Answer
time: 1ms
memory: 3920kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
45 14 44 70669
0 1 266130
1 2 372315
2 3 965349
3 4 119493
4 5 190522
5 6 506822
6 7 45330
7 8 423189
8 9 748532
9 10 653554
10 11 102552
11 12 90431
12 13 843259
13 14 422626
14 15 35334
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24...

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
31

result:

wrong answer 1st lines differ - on the 1st token, expected: '4', found: '31'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #36:

score: 9
Accepted
time: 0ms
memory: 3832kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
4 0 1 9
0 2 2
1 2 3
2 3 3

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
6

result:

ok 

Test #37:

score: 0
Accepted
time: 0ms
memory: 4092kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
4 0 1 8
0 2 2
1 2 3
2 3 100

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
5

result:

ok 

Test #38:

score: 0
Accepted
time: 1ms
memory: 4132kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
8 0 4 84
0 1 1
1 2 29
2 3 29
3 4 1
4 5 20
2 6 20
3 7 1

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
9

result:

ok 

Test #39:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
18 14 15 221112
8 10 15984
3 8 2664
6 10 5328
9 10 13320
5 10 23976
1 10 13320
3 4 5328
3 7 26640
3 11 23976
4 15 23976
6 17 18648
12 17 5328
11 13 13320
0 11 7992
15 16 5328
2 16 5328
13 14 2664

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
14

result:

ok 

Test #40:

score: 0
Accepted
time: 0ms
memory: 4128kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
19 3 9 11232111
13 14 174955
0 13 69982
10 14 209946
14 15 209946
12 14 104973
0 11 314919
0 3 314919
0 7 139964
5 10 209946
10 16 69982
4 10 104973
9 11 279928
9 17 349910
1 4 104973
3 18 209946
6 18 174955
7 8 314919
2 7 104973

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
28

result:

ok 

Test #41:

score: -9
Wrong Answer
time: 0ms
memory: 3832kb

input:

cc61ad56a4797fb3f5c9529f73ce6fcedd85669b
1
15 5 7 155966
1 4 964448
5 11 996819
9 10 330180
5 6 987448
11 12 704605
0 5 155967
8 14 596631
10 11 923917
0 14 560902
4 13 49411
1 7 856694
1 12 755799
2 14 488208
3 13 990480

output:

081ce3c351cbf526b37954b9ad30f2b531a7585c
OK
5

result:

wrong answer 1st lines differ - on the 1st token, expected: '2', found: '5'

Subtask #6:

score: 0
Skipped

Dependency #2:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #4:

0%

Subtask #9:

score: 0
Skipped

Dependency #1:

0%