답안 #1063164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063164	2024-08-17T14:48:00 Z	12345678	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	907 ms	36928 KB

reconstruction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e2+5, mx=1e5+5;

ll n, m, x, q, dsu[nx], l[mx], r[mx], lz, lst, sp;
vector<pair<ll, pair<ll, ll>>> edg;
vector<pair<ll, ll>> slope;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    edg.resize(m);
    for (auto &x:edg) cin>>x.second.first>>x.second.second>>x.first;
    sort(edg.begin(), edg.end());
    for (int i=0; i<m; i++)
    {
        l[i]=-1;
        r[i]=m;
        for (int j=1; j<=n; j++) dsu[j]=j;
        for (int k=i-1; k>=0; k--)
        {
            dsu[find(edg[k].second.first)]=find(edg[k].second.second);
            if (find(edg[i].second.first)==find(edg[i].second.second)) 
            {
                l[i]=k, r[l[i]]=i;
                break;
            }
        }
    }
    for (int i=0; i<m; i++)
    {
        //cout<<"edge "<<edg[i].second.first<<' '<<edg[i].second.second<<' '<<edg[i].first<<' '<<l[i]<<' '<<r[i]<<'\n';
        if (l[i]==-1) lz+=edg[i].first, slope.push_back({0, -1}), slope.push_back({edg[i].first, 1});
        else
        {
            ll loc=(edg[l[i]].first+edg[i].first+1)/2;
            slope.push_back({loc, -1});
            slope.push_back({edg[i].first, 1});
        }
        if (r[i]==m) slope.push_back({edg[i].first, 1});
        else
        {
            ll loc=(edg[i].first+edg[r[i]].first)/2;
            slope.push_back({edg[i].first, 1});
            slope.push_back({loc, -1});
        }
    }
    sort(slope.begin(), slope.end());
    reverse(slope.begin(), slope.end());
    cin>>q;
    while (q--)
    {
        cin>>x;
        while (!slope.empty()&&slope.back().first<=x)
        {
            //cout<<"here "<<sp<<' '<<slope.back().first<<'\n';
            lz+=(slope.back().first-lst)*sp;
            sp+=slope.back().second;
            lst=slope.back().first;
            slope.pop_back();
        }
        cout<<lz+sp*(x-lst)<<'\n';
    }
}

Subtask #1
3.0 / 3.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	344 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	344 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	348 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct
16	Correct	348 KB	Output is correct
17	Correct	348 KB	Output is correct
18	Correct	348 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	730 ms	15412 KB	Output is correct
21	Correct	360 ms	15560 KB	Output is correct
22	Correct	390 ms	15904 KB	Output is correct
23	Correct	460 ms	15560 KB	Output is correct
24	Correct	599 ms	15904 KB	Output is correct
25	Correct	785 ms	15560 KB	Output is correct
26	Correct	770 ms	15936 KB	Output is correct
27	Correct	763 ms	15812 KB	Output is correct
28	Correct	741 ms	15980 KB	Output is correct
29	Correct	541 ms	16012 KB	Output is correct
30	Correct	778 ms	16328 KB	Output is correct
31	Correct	774 ms	15160 KB	Output is correct
32	Correct	805 ms	16356 KB	Output is correct
33	Correct	762 ms	15196 KB	Output is correct
34	Correct	260 ms	14596 KB	Output is correct
35	Correct	783 ms	15304 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	472 ms	34080 KB	Output is correct
5	Correct	491 ms	34232 KB	Output is correct
6	Correct	483 ms	34872 KB	Output is correct
7	Correct	396 ms	35716 KB	Output is correct
8	Correct	375 ms	35404 KB	Output is correct
9	Correct	290 ms	35884 KB	Output is correct
10	Correct	469 ms	34996 KB	Output is correct
11	Correct	358 ms	36928 KB	Output is correct

Subtask #4
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	129 ms	22356 KB	Output is correct
21	Correct	126 ms	22612 KB	Output is correct
22	Correct	128 ms	22516 KB	Output is correct
23	Correct	150 ms	22580 KB	Output is correct
24	Correct	164 ms	22500 KB	Output is correct
25	Correct	156 ms	22552 KB	Output is correct
26	Correct	155 ms	22352 KB	Output is correct
27	Correct	138 ms	22392 KB	Output is correct
28	Correct	126 ms	22352 KB	Output is correct
29	Correct	144 ms	22352 KB	Output is correct
30	Correct	138 ms	22576 KB	Output is correct
31	Correct	159 ms	22368 KB	Output is correct
32	Correct	132 ms	23008 KB	Output is correct
33	Correct	180 ms	22392 KB	Output is correct

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	730 ms	15412 KB	Output is correct
21	Correct	360 ms	15560 KB	Output is correct
22	Correct	390 ms	15904 KB	Output is correct
23	Correct	460 ms	15560 KB	Output is correct
24	Correct	599 ms	15904 KB	Output is correct
25	Correct	785 ms	15560 KB	Output is correct
26	Correct	770 ms	15936 KB	Output is correct
27	Correct	763 ms	15812 KB	Output is correct
28	Correct	741 ms	15980 KB	Output is correct
29	Correct	541 ms	16012 KB	Output is correct
30	Correct	778 ms	16328 KB	Output is correct
31	Correct	774 ms	15160 KB	Output is correct
32	Correct	805 ms	16356 KB	Output is correct
33	Correct	762 ms	15196 KB	Output is correct
34	Correct	260 ms	14596 KB	Output is correct
35	Correct	783 ms	15304 KB	Output is correct
36	Correct	749 ms	16252 KB	Output is correct
37	Correct	373 ms	14536 KB	Output is correct
38	Correct	405 ms	16376 KB	Output is correct
39	Correct	506 ms	15304 KB	Output is correct
40	Correct	603 ms	15700 KB	Output is correct
41	Correct	810 ms	16096 KB	Output is correct
42	Correct	749 ms	15032 KB	Output is correct
43	Correct	734 ms	16328 KB	Output is correct
44	Correct	714 ms	16168 KB	Output is correct
45	Correct	502 ms	16360 KB	Output is correct
46	Correct	730 ms	15656 KB	Output is correct
47	Correct	759 ms	15384 KB	Output is correct
48	Correct	747 ms	14840 KB	Output is correct
49	Correct	766 ms	16072 KB	Output is correct
50	Correct	250 ms	15300 KB	Output is correct
51	Correct	748 ms	16312 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	730 ms	15412 KB	Output is correct
21	Correct	360 ms	15560 KB	Output is correct
22	Correct	390 ms	15904 KB	Output is correct
23	Correct	460 ms	15560 KB	Output is correct
24	Correct	599 ms	15904 KB	Output is correct
25	Correct	785 ms	15560 KB	Output is correct
26	Correct	770 ms	15936 KB	Output is correct
27	Correct	763 ms	15812 KB	Output is correct
28	Correct	741 ms	15980 KB	Output is correct
29	Correct	541 ms	16012 KB	Output is correct
30	Correct	778 ms	16328 KB	Output is correct
31	Correct	774 ms	15160 KB	Output is correct
32	Correct	805 ms	16356 KB	Output is correct
33	Correct	762 ms	15196 KB	Output is correct
34	Correct	260 ms	14596 KB	Output is correct
35	Correct	783 ms	15304 KB	Output is correct
36	Correct	0 ms	344 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	1 ms	468 KB	Output is correct
39	Correct	472 ms	34080 KB	Output is correct
40	Correct	491 ms	34232 KB	Output is correct
41	Correct	483 ms	34872 KB	Output is correct
42	Correct	396 ms	35716 KB	Output is correct
43	Correct	375 ms	35404 KB	Output is correct
44	Correct	290 ms	35884 KB	Output is correct
45	Correct	469 ms	34996 KB	Output is correct
46	Correct	358 ms	36928 KB	Output is correct
47	Correct	0 ms	348 KB	Output is correct
48	Correct	129 ms	22356 KB	Output is correct
49	Correct	126 ms	22612 KB	Output is correct
50	Correct	128 ms	22516 KB	Output is correct
51	Correct	150 ms	22580 KB	Output is correct
52	Correct	164 ms	22500 KB	Output is correct
53	Correct	156 ms	22552 KB	Output is correct
54	Correct	155 ms	22352 KB	Output is correct
55	Correct	138 ms	22392 KB	Output is correct
56	Correct	126 ms	22352 KB	Output is correct
57	Correct	144 ms	22352 KB	Output is correct
58	Correct	138 ms	22576 KB	Output is correct
59	Correct	159 ms	22368 KB	Output is correct
60	Correct	132 ms	23008 KB	Output is correct
61	Correct	180 ms	22392 KB	Output is correct
62	Correct	749 ms	16252 KB	Output is correct
63	Correct	373 ms	14536 KB	Output is correct
64	Correct	405 ms	16376 KB	Output is correct
65	Correct	506 ms	15304 KB	Output is correct
66	Correct	603 ms	15700 KB	Output is correct
67	Correct	810 ms	16096 KB	Output is correct
68	Correct	749 ms	15032 KB	Output is correct
69	Correct	734 ms	16328 KB	Output is correct
70	Correct	714 ms	16168 KB	Output is correct
71	Correct	502 ms	16360 KB	Output is correct
72	Correct	730 ms	15656 KB	Output is correct
73	Correct	759 ms	15384 KB	Output is correct
74	Correct	747 ms	14840 KB	Output is correct
75	Correct	766 ms	16072 KB	Output is correct
76	Correct	250 ms	15300 KB	Output is correct
77	Correct	748 ms	16312 KB	Output is correct
78	Correct	864 ms	33728 KB	Output is correct
79	Correct	477 ms	35232 KB	Output is correct
80	Correct	528 ms	33248 KB	Output is correct
81	Correct	572 ms	34232 KB	Output is correct
82	Correct	733 ms	33384 KB	Output is correct
83	Correct	907 ms	33852 KB	Output is correct
84	Correct	873 ms	33956 KB	Output is correct
85	Correct	880 ms	32208 KB	Output is correct
86	Correct	844 ms	33532 KB	Output is correct
87	Correct	624 ms	34236 KB	Output is correct
88	Correct	860 ms	33564 KB	Output is correct
89	Correct	870 ms	32460 KB	Output is correct
90	Correct	861 ms	33472 KB	Output is correct
91	Correct	855 ms	32188 KB	Output is correct
92	Correct	384 ms	36800 KB	Output is correct
93	Correct	847 ms	34748 KB	Output is correct

답안 #1063164

Compilation message

Subtask #1 3.0 / 3.0

Subtask #2 4.0 / 4.0

Subtask #3 7.0 / 7.0

Subtask #4 28.0 / 28.0

Subtask #5 35.0 / 35.0

Subtask #6 23.0 / 23.0

Subtask #1
3.0 / 3.0

Subtask #2
4.0 / 4.0

Subtask #3
7.0 / 7.0

Subtask #4
28.0 / 28.0

Subtask #5
35.0 / 35.0

Subtask #6
23.0 / 23.0