답안 #60307 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60307	2018-07-24T01:01:41 Z	XmtosX	Construction of Highway (JOI18_construction)	C++17	100 / 100	855 ms	89352 KB

construction

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,c[N],a[N],b[N],sz[N],par[N],nxt[N],lvl[N],bit[N];
vector<int> v[N];
vector<pair<int,int> > V[N];
void update (int x,int val)
{
    while (x<N)
    {
        bit[x]+=val;
        x+= (x&(-x));
    }
}
int query (int x)
{
    int sum=0;
    while (x)
    {
        sum+= bit[x];
        x-= (x&(-x));
    }
    return sum;
}
void dfs (int x,int p)
{
    par[x]=p;
    sz[x]=1;
    lvl[x]=lvl[p]+1;
    for (int i=0;i<v[x].size();i++)
    {
        dfs(v[x][i],x);
        sz[x]+=sz[v[x][i]];
        if (sz[v[x][i]]>sz[v[x][0]])
            swap(v[x][i],v[x][0]);
    }
}
void hld (int x)
{
    for (int i=0;i<v[x].size();i++)
    {
        if (i==0)
            nxt[v[x][i]]=nxt[x];
        else
            nxt[v[x][i]]=v[x][i];
        hld(v[x][i]);
    }
}
long long solve(int x)
{
    vector <pair<int,int> > p;
    vector <int> v;
    int z=x;
    while (x)
    {
        int l= (lvl[x]-lvl[nxt[x]]+1);
        x=nxt[x];
        vector <pair<int,int> > o;
        for (int i=V[x].size()-1;i>=0;i--)
        {
            int cnt=V[x][i].first;
            int y=V[x][i].second;

            if (cnt<l)
            {
                o.push_back(V[x][i]);
                v.push_back(y);
                l-=cnt;
            }
            else
            {
                o.push_back(make_pair(l,y));
                v.push_back(y);
                break;
            }
        }
        for (int i=o.size()-1;i>=0;i--)
            p.push_back(o[i]);
        x=par[x];
    }
    reverse(p.begin(),p.end());
    v.push_back(0);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    for (int i=0;i<=v.size();i++)
        bit[i]=0;
    long long ans=0;
    int tot=0;
    for (int i=0;i<p.size();i++)
    {
        int y=p[i].second;
        long long cnt=p[i].first;
        x= lower_bound(v.begin(),v.end(),y)-v.begin();
        ans+= cnt*(tot-query(x));
        tot+=cnt;
        update(x,cnt);
    }
    return ans;
}
void change (int x)
{
    int q=c[x];
    while (x)
    {
        int l= lvl[x]-lvl[nxt[x]]+1;
        int y=l;
        x=nxt[x];
        while (!V[x].empty())
        {
            int i= (V[x].size()-1);
            int cnt=(V[x][i].first);
            if (cnt<=l)
            {
                l-=cnt;
                V[x].pop_back();
            }
            else
            {
                V[x][i].first-=l;
                break;
            }
        }
        if (!V[x].empty()&&V[x][V[x].size()-1].second==q)
            V[x][V[x].size()-1].first+=y;
        else
            V[x].push_back({y,q});
        x=par[x];
    }
}
int main()
{
    cin >>n;
    for (int i=1;i<=n;i++)
        cin >>c[i];
    for (int i=0;i<n-1;i++)
    {
        cin >>a[i]>>b[i];
        v[a[i]].push_back(b[i]);
    }
    dfs(1,0);
    nxt[1]=1;
    hld(1);
    V[1].push_back({1,c[1]});
    for (int i=0;i<n-1;i++)
    {
        cout <<solve(a[i])<<"\n";
        change(b[i]);
    }
    return 0;
}
/*
5
1 2 3 4 5
1 2
2 3
2 4
3 5
*/
/*
10
1 7 3 4 8 6 2 9 10 5
1 2
1 3
2 4
3 5
2 6
3 7
4 8
5 9
6 10
*/

Compilation message

construction.cpp: In function 'void dfs(int, int)':
construction.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
construction.cpp: In function 'void hld(int)':
construction.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                  ~^~~~~~~~~~~~
construction.cpp: In function 'long long int solve(int)':
construction.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<=v.size();i++)
                  ~^~~~~~~~~~
construction.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<p.size();i++)
                  ~^~~~~~~~~
construction.cpp:53:9: warning: unused variable 'z' [-Wunused-variable]
     int z=x;
         ^

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	7 ms	5212 KB	Output is correct
3	Correct	9 ms	5456 KB	Output is correct
4	Correct	9 ms	5456 KB	Output is correct
5	Correct	12 ms	5456 KB	Output is correct
6	Correct	10 ms	5468 KB	Output is correct
7	Correct	11 ms	5500 KB	Output is correct
8	Correct	10 ms	5544 KB	Output is correct
9	Correct	9 ms	5560 KB	Output is correct
10	Correct	10 ms	5584 KB	Output is correct
11	Correct	9 ms	5600 KB	Output is correct
12	Correct	9 ms	5672 KB	Output is correct
13	Correct	10 ms	5672 KB	Output is correct
14	Correct	8 ms	5672 KB	Output is correct
15	Correct	9 ms	5716 KB	Output is correct
16	Correct	11 ms	5804 KB	Output is correct
17	Correct	10 ms	5804 KB	Output is correct
18	Correct	12 ms	5804 KB	Output is correct
19	Correct	10 ms	5844 KB	Output is correct
20	Correct	8 ms	5844 KB	Output is correct
21	Correct	8 ms	5844 KB	Output is correct
22	Correct	11 ms	5856 KB	Output is correct
23	Correct	10 ms	5860 KB	Output is correct
24	Correct	8 ms	5860 KB	Output is correct
25	Correct	9 ms	5912 KB	Output is correct
26	Correct	9 ms	5912 KB	Output is correct
27	Correct	8 ms	5912 KB	Output is correct
28	Correct	10 ms	5912 KB	Output is correct
29	Correct	8 ms	5912 KB	Output is correct
30	Correct	8 ms	5916 KB	Output is correct
31	Correct	10 ms	6048 KB	Output is correct
32	Correct	9 ms	6048 KB	Output is correct
33	Correct	10 ms	6048 KB	Output is correct
34	Correct	11 ms	6048 KB	Output is correct
35	Correct	9 ms	6048 KB	Output is correct
36	Correct	9 ms	6048 KB	Output is correct
37	Correct	9 ms	6048 KB	Output is correct
38	Correct	8 ms	6048 KB	Output is correct
39	Correct	10 ms	6048 KB	Output is correct
40	Correct	9 ms	6048 KB	Output is correct
41	Correct	9 ms	6048 KB	Output is correct
42	Correct	10 ms	6096 KB	Output is correct
43	Correct	8 ms	6096 KB	Output is correct
44	Correct	10 ms	6096 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	7 ms	5212 KB	Output is correct
3	Correct	9 ms	5456 KB	Output is correct
4	Correct	9 ms	5456 KB	Output is correct
5	Correct	12 ms	5456 KB	Output is correct
6	Correct	10 ms	5468 KB	Output is correct
7	Correct	11 ms	5500 KB	Output is correct
8	Correct	10 ms	5544 KB	Output is correct
9	Correct	9 ms	5560 KB	Output is correct
10	Correct	10 ms	5584 KB	Output is correct
11	Correct	9 ms	5600 KB	Output is correct
12	Correct	9 ms	5672 KB	Output is correct
13	Correct	10 ms	5672 KB	Output is correct
14	Correct	8 ms	5672 KB	Output is correct
15	Correct	9 ms	5716 KB	Output is correct
16	Correct	11 ms	5804 KB	Output is correct
17	Correct	10 ms	5804 KB	Output is correct
18	Correct	12 ms	5804 KB	Output is correct
19	Correct	10 ms	5844 KB	Output is correct
20	Correct	8 ms	5844 KB	Output is correct
21	Correct	8 ms	5844 KB	Output is correct
22	Correct	11 ms	5856 KB	Output is correct
23	Correct	10 ms	5860 KB	Output is correct
24	Correct	8 ms	5860 KB	Output is correct
25	Correct	9 ms	5912 KB	Output is correct
26	Correct	9 ms	5912 KB	Output is correct
27	Correct	8 ms	5912 KB	Output is correct
28	Correct	10 ms	5912 KB	Output is correct
29	Correct	8 ms	5912 KB	Output is correct
30	Correct	8 ms	5916 KB	Output is correct
31	Correct	10 ms	6048 KB	Output is correct
32	Correct	9 ms	6048 KB	Output is correct
33	Correct	10 ms	6048 KB	Output is correct
34	Correct	11 ms	6048 KB	Output is correct
35	Correct	9 ms	6048 KB	Output is correct
36	Correct	9 ms	6048 KB	Output is correct
37	Correct	9 ms	6048 KB	Output is correct
38	Correct	8 ms	6048 KB	Output is correct
39	Correct	10 ms	6048 KB	Output is correct
40	Correct	9 ms	6048 KB	Output is correct
41	Correct	9 ms	6048 KB	Output is correct
42	Correct	10 ms	6096 KB	Output is correct
43	Correct	8 ms	6096 KB	Output is correct
44	Correct	10 ms	6096 KB	Output is correct
45	Correct	10 ms	6096 KB	Output is correct
46	Correct	24 ms	6316 KB	Output is correct
47	Correct	27 ms	6432 KB	Output is correct
48	Correct	26 ms	6468 KB	Output is correct
49	Correct	16 ms	6800 KB	Output is correct
50	Correct	20 ms	6800 KB	Output is correct
51	Correct	21 ms	6824 KB	Output is correct
52	Correct	19 ms	7028 KB	Output is correct
53	Correct	14 ms	7028 KB	Output is correct
54	Correct	17 ms	7088 KB	Output is correct
55	Correct	17 ms	7196 KB	Output is correct
56	Correct	25 ms	7196 KB	Output is correct
57	Correct	24 ms	7196 KB	Output is correct
58	Correct	24 ms	7196 KB	Output is correct
59	Correct	26 ms	7312 KB	Output is correct
60	Correct	29 ms	7432 KB	Output is correct
61	Correct	23 ms	7544 KB	Output is correct
62	Correct	19 ms	7588 KB	Output is correct
63	Correct	17 ms	7696 KB	Output is correct
64	Correct	19 ms	7696 KB	Output is correct
65	Correct	21 ms	7768 KB	Output is correct
66	Correct	18 ms	7868 KB	Output is correct
67	Correct	23 ms	7868 KB	Output is correct
68	Correct	17 ms	8012 KB	Output is correct
69	Correct	15 ms	8056 KB	Output is correct
70	Correct	17 ms	8112 KB	Output is correct
71	Correct	15 ms	8160 KB	Output is correct
72	Correct	22 ms	8208 KB	Output is correct
73	Correct	26 ms	8264 KB	Output is correct
74	Correct	16 ms	8332 KB	Output is correct
75	Correct	18 ms	8332 KB	Output is correct
76	Correct	15 ms	8332 KB	Output is correct
77	Correct	15 ms	8384 KB	Output is correct
78	Correct	14 ms	8448 KB	Output is correct
79	Correct	16 ms	8496 KB	Output is correct
80	Correct	17 ms	8544 KB	Output is correct
81	Correct	20 ms	8592 KB	Output is correct
82	Correct	18 ms	8656 KB	Output is correct
83	Correct	17 ms	8720 KB	Output is correct
84	Correct	19 ms	8828 KB	Output is correct
85	Correct	15 ms	8832 KB	Output is correct
86	Correct	17 ms	8880 KB	Output is correct

Subtask #3
84.0 / 84.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	7 ms	5212 KB	Output is correct
3	Correct	9 ms	5456 KB	Output is correct
4	Correct	9 ms	5456 KB	Output is correct
5	Correct	12 ms	5456 KB	Output is correct
6	Correct	10 ms	5468 KB	Output is correct
7	Correct	11 ms	5500 KB	Output is correct
8	Correct	10 ms	5544 KB	Output is correct
9	Correct	9 ms	5560 KB	Output is correct
10	Correct	10 ms	5584 KB	Output is correct
11	Correct	9 ms	5600 KB	Output is correct
12	Correct	9 ms	5672 KB	Output is correct
13	Correct	10 ms	5672 KB	Output is correct
14	Correct	8 ms	5672 KB	Output is correct
15	Correct	9 ms	5716 KB	Output is correct
16	Correct	11 ms	5804 KB	Output is correct
17	Correct	10 ms	5804 KB	Output is correct
18	Correct	12 ms	5804 KB	Output is correct
19	Correct	10 ms	5844 KB	Output is correct
20	Correct	8 ms	5844 KB	Output is correct
21	Correct	8 ms	5844 KB	Output is correct
22	Correct	11 ms	5856 KB	Output is correct
23	Correct	10 ms	5860 KB	Output is correct
24	Correct	8 ms	5860 KB	Output is correct
25	Correct	9 ms	5912 KB	Output is correct
26	Correct	9 ms	5912 KB	Output is correct
27	Correct	8 ms	5912 KB	Output is correct
28	Correct	10 ms	5912 KB	Output is correct
29	Correct	8 ms	5912 KB	Output is correct
30	Correct	8 ms	5916 KB	Output is correct
31	Correct	10 ms	6048 KB	Output is correct
32	Correct	9 ms	6048 KB	Output is correct
33	Correct	10 ms	6048 KB	Output is correct
34	Correct	11 ms	6048 KB	Output is correct
35	Correct	9 ms	6048 KB	Output is correct
36	Correct	9 ms	6048 KB	Output is correct
37	Correct	9 ms	6048 KB	Output is correct
38	Correct	8 ms	6048 KB	Output is correct
39	Correct	10 ms	6048 KB	Output is correct
40	Correct	9 ms	6048 KB	Output is correct
41	Correct	9 ms	6048 KB	Output is correct
42	Correct	10 ms	6096 KB	Output is correct
43	Correct	8 ms	6096 KB	Output is correct
44	Correct	10 ms	6096 KB	Output is correct
45	Correct	10 ms	6096 KB	Output is correct
46	Correct	24 ms	6316 KB	Output is correct
47	Correct	27 ms	6432 KB	Output is correct
48	Correct	26 ms	6468 KB	Output is correct
49	Correct	16 ms	6800 KB	Output is correct
50	Correct	20 ms	6800 KB	Output is correct
51	Correct	21 ms	6824 KB	Output is correct
52	Correct	19 ms	7028 KB	Output is correct
53	Correct	14 ms	7028 KB	Output is correct
54	Correct	17 ms	7088 KB	Output is correct
55	Correct	17 ms	7196 KB	Output is correct
56	Correct	25 ms	7196 KB	Output is correct
57	Correct	24 ms	7196 KB	Output is correct
58	Correct	24 ms	7196 KB	Output is correct
59	Correct	26 ms	7312 KB	Output is correct
60	Correct	29 ms	7432 KB	Output is correct
61	Correct	23 ms	7544 KB	Output is correct
62	Correct	19 ms	7588 KB	Output is correct
63	Correct	17 ms	7696 KB	Output is correct
64	Correct	19 ms	7696 KB	Output is correct
65	Correct	21 ms	7768 KB	Output is correct
66	Correct	18 ms	7868 KB	Output is correct
67	Correct	23 ms	7868 KB	Output is correct
68	Correct	17 ms	8012 KB	Output is correct
69	Correct	15 ms	8056 KB	Output is correct
70	Correct	17 ms	8112 KB	Output is correct
71	Correct	15 ms	8160 KB	Output is correct
72	Correct	22 ms	8208 KB	Output is correct
73	Correct	26 ms	8264 KB	Output is correct
74	Correct	16 ms	8332 KB	Output is correct
75	Correct	18 ms	8332 KB	Output is correct
76	Correct	15 ms	8332 KB	Output is correct
77	Correct	15 ms	8384 KB	Output is correct
78	Correct	14 ms	8448 KB	Output is correct
79	Correct	16 ms	8496 KB	Output is correct
80	Correct	17 ms	8544 KB	Output is correct
81	Correct	20 ms	8592 KB	Output is correct
82	Correct	18 ms	8656 KB	Output is correct
83	Correct	17 ms	8720 KB	Output is correct
84	Correct	19 ms	8828 KB	Output is correct
85	Correct	15 ms	8832 KB	Output is correct
86	Correct	17 ms	8880 KB	Output is correct
87	Correct	46 ms	9484 KB	Output is correct
88	Correct	118 ms	11264 KB	Output is correct
89	Correct	527 ms	17892 KB	Output is correct
90	Correct	545 ms	20016 KB	Output is correct
91	Correct	502 ms	22072 KB	Output is correct
92	Correct	345 ms	28692 KB	Output is correct
93	Correct	283 ms	30892 KB	Output is correct
94	Correct	407 ms	32944 KB	Output is correct
95	Correct	315 ms	34220 KB	Output is correct
96	Correct	306 ms	36332 KB	Output is correct
97	Correct	327 ms	38416 KB	Output is correct
98	Correct	332 ms	40616 KB	Output is correct
99	Correct	387 ms	40872 KB	Output is correct
100	Correct	759 ms	40872 KB	Output is correct
101	Correct	811 ms	42500 KB	Output is correct
102	Correct	753 ms	44748 KB	Output is correct
103	Correct	855 ms	46824 KB	Output is correct
104	Correct	337 ms	51124 KB	Output is correct
105	Correct	363 ms	53356 KB	Output is correct
106	Correct	328 ms	55368 KB	Output is correct
107	Correct	424 ms	55368 KB	Output is correct
108	Correct	552 ms	55924 KB	Output is correct
109	Correct	621 ms	57836 KB	Output is correct
110	Correct	293 ms	63608 KB	Output is correct
111	Correct	291 ms	64832 KB	Output is correct
112	Correct	288 ms	66476 KB	Output is correct
113	Correct	334 ms	66476 KB	Output is correct
114	Correct	675 ms	66476 KB	Output is correct
115	Correct	837 ms	67420 KB	Output is correct
116	Correct	267 ms	70972 KB	Output is correct
117	Correct	292 ms	71468 KB	Output is correct
118	Correct	286 ms	72996 KB	Output is correct
119	Correct	317 ms	74460 KB	Output is correct
120	Correct	313 ms	76572 KB	Output is correct
121	Correct	313 ms	77768 KB	Output is correct
122	Correct	350 ms	79152 KB	Output is correct
123	Correct	391 ms	81704 KB	Output is correct
124	Correct	313 ms	83080 KB	Output is correct
125	Correct	320 ms	84628 KB	Output is correct
126	Correct	282 ms	86796 KB	Output is correct
127	Correct	396 ms	87928 KB	Output is correct
128	Correct	455 ms	89352 KB	Output is correct

답안 #60307

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 9.0 / 9.0

Subtask #3 84.0 / 84.0

Subtask #1
7.0 / 7.0

Subtask #2
9.0 / 9.0

Subtask #3
84.0 / 84.0