QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#463581#8253. Very Important Edge36champWA 2265ms295244kbC++205.7kb2024-07-05 01:31:592024-07-05 01:31:59

Judging History

This is the latest submission verdict.

  • [2024-07-05 01:31:59]
  • Judged
  • Verdict: WA
  • Time: 2265ms
  • Memory: 295244kb
  • [2024-07-05 01:31:59]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

const ll INF = 1LL << 62;
int n, m;

class DSU{
    public:
        vector<int> parent, rnk;

        DSU(int n) {
            parent = vector<int>(n, 0);
            rnk = parent;
            for(int i=0; i<n; i++) make_set(i);
        }

        void log()
        {
            for(int x: parent) cout << x << " ";
            cout << "\n";
        }

        void make_set(int v) {
            parent[v] = v;
            rnk[v] = 0;
        }

        int find_set(int v) {
            if(v < 0) return v;
            if (v == parent[v])
                return v;
            parent[v] = find_set(parent[v]);
            return parent[v];
        }

        void union_sets(int a, int b) {
            if(a<0 || b<0) return;
            a = find_set(a);
            b = find_set(b);
            if (a != b) {
                if (rnk[a] < rnk[b])
                    swap(a, b);
                parent[b] = a;
                if (rnk[a] == rnk[b])
                {
                    rnk[a]++;
                }
            }
        }
};

class segTree{
    public:
        vector<ll> t;

        segTree(int n)
        {
            t = vector<ll>(4 * n, INF);
        }

        void build(vector<ll> &a, ll v, ll tl, ll tr) {
            if (tl == tr) {
                t[v] = a[tl];
            } else {
                ll tm = (tl + tr) / 2;
                build(a, v*2, tl, tm);
                build(a, v*2+1, tm+1, tr);
                t[v] = t[v*2] + t[v*2+1];
            }
        }

        ll min(ll v, ll tl, ll tr, ll l, ll r) {
            if (l > r)
                return INF;
            if (l == tl && r == tr) {
                return t[v];
            }
            ll tm = (tl + tr) / 2;
            return std::min(min(v*2, tl, tm, l, std::min(r, tm))
                   , min(v*2+1, tm+1, tr, max(l, tm+1), r));
        }

        void update(ll v, ll tl, ll tr, ll pos, ll new_val) {
            if (tl == tr) {
                t[v] = new_val;
            } else {
                ll tm = (tl + tr) / 2;
                if (pos <= tm)
                    update(v*2, tl, tm, pos, new_val);
                else
                    update(v*2+1, tm+1, tr, pos, new_val);
                t[v] = std::min(t[v*2], t[v*2+1]);
            }
        }
};


void dfs(int p, vector<vector<vector<ll>>> &adj, vector<vector<int>> &up, vector<int> &depth, vector<ll> &v)
{
    for(vector<ll> edge: adj[p])
    {
        ll c = edge[0], val = edge[1];

        if(c == up[p][0]) continue;

        v[c] = val;
        depth[c] = depth[p] + 1;
        up[c][0] = p;
        for(int i=1; i<=19; i++) up[p][i] = up[up[c][i-1]][i-1];
        dfs(c, adj, up, depth, v);
    }
}

int lca(vector<vector<int>> &up, int u, int v, int d_u, int d_v)
{
    if(d_v < d_u)
    {
        swap(u, v);
        swap(d_u, d_v);
    }

    //cout << "LCA " << u << " " << v << " ";

    for(int i=19; i>=0; i--)
    {
        if(d_u + (1 << i) <= d_v)
        {
            v = up[v][i];
            d_v -= 1 << i;
        }
    }

    if(u == v) return u;

    for(int i=19; i>=0; i--)
    {
        if(up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

void dfs2(int p, int &pos, vector<vector<vector<ll>>> &adj, vector<vector<vector<ll>>> &adj2, vector<vector<int>> &up, vector<int> &left, vector<vector<int>> &del, vector<ll> &l, segTree &T, vector<int> &depth)
{
    //cout << "DFS 2 : " << p << " " << pos << "\n";

    left[p] = pos;

    for(vector<ll> edge: adj[p])
    {
        ll c = edge[0], val = edge[1];

        if(c == up[p][0]) continue;

        dfs2(c, pos, adj, adj2, up, left, del, l, T, depth);
    }

    for(vector<ll> edge: adj2[p])
    {
        ll c = edge[0], val = edge[1];

        T.update(1, 0, 2*m-2*n+1, pos, val);
        del[lca(up, p, c, depth[p], depth[c])].pb(pos);

        //cout << "OK\n";

        pos++;
    }

    for(int index: del[p])
    {
        T.update(1, 0, 2*m-2*n+1, index, INF);
    }

    /*for(ll x: T.t) cout << x << " ";
    cout << "\n";*/

    //cout << "FIND MIN " << left[p] << " " << pos - 1 << " = ";

    l[p] = T.min(1, 0, 2*m-2*n+1, left[p], pos - 1);

    //cout << l[p] << "\n";
}

int main()
{
    //ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m;

	vector<vector<ll>> edge(m, {0, 0, 0});
	vector<vector<int>> up(n + 1, vector<int>(20, 0));

	ll ans = 0;
	for(int i=0; i<m; i++) cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	sort(edge.begin(), edge.end());

	vector<vector<vector<ll>>> adj(n + 1), adj2(n + 1);
	DSU a(n + 1);
	for(int i=0; i<m; i++)
    {
        int u = edge[i][1], v = edge[i][2], c = edge[i][0];
        if(a.find_set(u) != a.find_set(v))
        {
            a.union_sets(u, v);
            ans += c;
            adj[u].pb({v, c});
            adj[v].pb({u, c});
        }
        else
        {
            adj2[u].pb({v, c});
            adj2[v].pb({u, c});
        }
    }

    vector<int> depth(n + 1, 0);
    vector<ll> val(n + 1);
    dfs(1, adj, up, depth, val);

    /*for(int x: depth) cout << x << " ";
    cout << "\n";*/

    segTree T(2*m - 2*n + 2);

    vector<int> left(n + 1);
    vector<ll> l(n+1, INF);
    vector<vector<int>> del(n+1);
    int pos = 0;
    dfs2(1, pos, adj, adj2, up, left, del, l, T, depth);

    //for(ll x: l) cout << x << " ";

    ll M = 0;
    for(int i=2; i<=n; i++) M = max(M, l[i] - val[i]);

    cout << ans + M;
}

詳細信息

Test #1:

score: 100
Accepted
time: 743ms
memory: 123104kb

input:

1000 499500
26 715 732723
850 918 507404
276 643 372190
67 702 972051
397 777 337003
178 185 863117
61 151 943008
83 581 731622
99 501 3260
301 588 948638
17 908 147104
193 480 94512
347 415 416562
519 912 627431
70 959 86892
333 573 757685
129 197 181261
224 636 259176
335 426 567962
193 339 70097
...

output:

1121154

result:

ok single line: '1121154'

Test #2:

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

input:

3 3
1 2 1
2 3 2
1 3 2

output:

4

result:

ok single line: '4'

Test #3:

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

input:

4 5
2 3 5
1 2 2
1 3 4
1 4 2
3 4 3

output:

10

result:

ok single line: '10'

Test #4:

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

input:

5 7
2 5 8
1 3 19
4 5 9
1 5 15
1 2 14
3 4 16
2 4 15

output:

54

result:

ok single line: '54'

Test #5:

score: 0
Accepted
time: 721ms
memory: 122736kb

input:

1000 499500
857 965 96030
394 688 78612
440 754 495692
48 297 76650
206 975 200873
790 854 325696
307 384 472048
94 958 278751
601 806 136479
880 988 278407
265 813 315222
114 470 208185
172 332 425333
504 669 12025
266 315 400789
61 894 120668
675 972 228141
604 855 494399
116 496 234186
116 888 21...

output:

627123

result:

ok single line: '627123'

Test #6:

score: 0
Accepted
time: 11ms
memory: 6036kb

input:

1000 10000
894 939 776049
780 873 504700
126 161 227849
221 391 589404
562 661 697593
8 495 975484
13 527 481938
711 908 92209
147 616 682518
117 849 292092
231 463 868315
296 372 308904
458 886 970257
44 415 858179
2 352 402538
340 431 276296
87 744 48795
30 146 526326
35 109 788908
551 742 146887
...

output:

64112840

result:

ok single line: '64112840'

Test #7:

score: 0
Accepted
time: 2265ms
memory: 295244kb

input:

100000 1000000
3496 42038 2
23760 54893 2
40179 73909 2
18246 58964 2
59829 97488 2
46535 89743 2
43598 88684 2
10025 15117 2
25372 39316 2
55988 99623 2
12242 94927 2
91339 99004 2
68898 82761 2
19117 49957 2
24435 85140 2
15302 78102 2
9038 89450 2
82914 88120 2
6227 67500 2
5298 26787 2
27614 518...

output:

100000

result:

ok single line: '100000'

Test #8:

score: 0
Accepted
time: 283ms
memory: 63728kb

input:

100000 150000
10397 97917 1
81023 97767 2
27616 48830 2
17714 90000 2
34151 34285 1
6030 96304 1
50786 80688 1
30193 63737 1
25856 97783 1
735 46702 2
24633 79153 1
27172 85261 1
18963 27646 1
68548 74906 1
45452 65265 2
20050 96249 1
42929 94752 1
30314 52715 2
17457 32389 1
79882 95851 1
20932 436...

output:

100000

result:

ok single line: '100000'

Test #9:

score: -100
Wrong Answer
time: 253ms
memory: 62500kb

input:

1000 249502
53 877 1
475 560 1
559 895 1
672 838 1
68 950 1
105 805 1
636 879 1
597 991 1
601 738 1
26 194 1
169 920 1
47 787 1
470 882 1
253 734 1
454 803 1
302 998 1
523 678 1
191 415 1
279 687 1
261 595 1
373 780 1
28 977 1
393 412 1
315 676 1
6 474 1
142 246 1
164 413 1
548 960 1
316 849 1
157 8...

output:

999

result:

wrong answer 1st lines differ - expected: '1000', found: '999'