oj.uz

Submission #85945

# Submission time Handle Problem Language Result Execution time Memory
85945 2018-11-23T07:53:31 Z bash Construction of Highway (JOI18_construction) C++17
100 / 100
 598 ms 187804 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
int a[111111];
int sz[111111];
int in[111111];
int rin[111111];
int t;
int out[111111];
deque<ii> chain[111111]; //heavy chain starting at vertex u
int nxt[111111];
vi adj[111111];
int par[111111];
int h[111111];
 
void addtochain(int u, int v)
{
	if(chain[u].empty()) chain[u].pb(mp(1,v));
	else if(chain[u].back().fi==v) chain[u].back().se++;
	else chain[u].pb(mp(v,1));
}
 
void dfs_sz(int v = 0)
{
    sz[v] = 1;
    for(auto &u: adj[v])
    {
		par[u] = v; h[u] = h[v] + 1;
        dfs_sz(u);
        sz[v] += sz[u];
        if(sz[u] > sz[adj[v][0]])
            swap(u, adj[v][0]);
    }
}
 
void dfs_hld(int v = 0)
{
    in[v] = t++;
    rin[in[v]] = v;
    for(auto u: adj[v])
    {
        nxt[u] = (u == adj[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
    out[v] = t;
}
 
int fen[111111];
int N;
 
void init(int n)
{
	N=n;
	for(int i=0;i<=N;i++) fen[i]=0;
}
 
void update(int pos, int v)
{
	pos++;
	for(;pos<=N;pos+=(pos&(-pos)))
	{
		fen[pos]+=v;
	}
}
 
int query(int pos)
{
	pos++;
	int sum=0;
	for(;pos;pos-=(pos&(-pos)))
	{
		sum+=fen[pos];
	}
	return sum;
}
 
ll calc_path(int u)
{
	vector<ii> V; vi coord;
	while(u!=-1)
	{
		int nu = nxt[u];
		int siz = h[u] - h[nu] + 1;
		vector<ii> tst;
		//cerr<<"CHAIN : "<<u<<' '<<nu<<'\n';
		for(int i=0;i<chain[nu].size();i++)
		{
			int cnt = chain[nu][i].fi; int v = chain[nu][i].se;
			if(cnt<=siz)
			{
				tst.pb(mp(cnt,v));
				siz-=cnt;
			}
			else
			{
				tst.pb(mp(siz,v));
				break;
			}
		}
		for(int i=int(tst.size())-1;i>=0;i--) 
		{
			V.pb(tst[i]); coord.pb(tst[i].se);
		}
		u=par[nu];
	}
	reverse(V.begin(),V.end());
	sort(coord.begin(),coord.end()); coord.erase(unique(coord.begin(),coord.end()),coord.end());
	//cerr<<coord.size()<<'\n';
	init(int(coord.size()));
	ll ans = 0; ll tot = 0;
	for(ii x:V)
	{
		x.se = lower_bound(coord.begin(),coord.end(),x.se)-coord.begin();
		ans += x.fi*(tot - query(x.se));
		//cerr<<x.fi<<' '<<x.se<<'\n';
		tot+=x.fi;
		update(x.se, x.fi);
	}
	//cerr<<'\n';
	return ans;
}
 
void addedge(int u, int v)
{
	while(u!=-1)
	{
		int nu = nxt[u];
		int siz = h[u] - h[nu] + 1;
		while(chain[nu].size()>0)
		{
			int cnt = chain[nu][0].fi;
			if(cnt<=siz)
			{
				chain[nu].pop_front();
				siz-=cnt;
			}
			else
			{
				chain[nu].front().fi -= siz;
				break;
			}
		}
		chain[nu].push_front(mp(h[u]-h[nu]+1, v));
		u=par[nu];
	}
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	nxt[0] = 0; addtochain(0,a[0]);
	vector<ii> edges;
	par[0]=-1;
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); edges.pb(mp(u,v));
	}
	dfs_sz(); dfs_hld();
	for(int i=0;i<n-1;i++)
	{
		cout<<calc_path(edges[i].fi)<<'\n';
		addedge(edges[i].se, a[edges[i].se]);
		//calc_path(edges[i].fi, edges[i].se);
	}
}

Compilation message

construction.cpp: In function 'll calc_path(int)':
construction.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<chain[nu].size();i++)
               ~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 77916 KB Output is correct
2 Correct 80 ms 78156 KB Output is correct
3 Correct 85 ms 78156 KB Output is correct
4 Correct 94 ms 78288 KB Output is correct
5 Correct 85 ms 78476 KB Output is correct
6 Correct 86 ms 78584 KB Output is correct
7 Correct 86 ms 78584 KB Output is correct
8 Correct 96 ms 78584 KB Output is correct
9 Correct 77 ms 78696 KB Output is correct
10 Correct 77 ms 78696 KB Output is correct
11 Correct 87 ms 78696 KB Output is correct
12 Correct 86 ms 78948 KB Output is correct
13 Correct 88 ms 78948 KB Output is correct
14 Correct 87 ms 78948 KB Output is correct
15 Correct 83 ms 78984 KB Output is correct
16 Correct 88 ms 78992 KB Output is correct
17 Correct 87 ms 78992 KB Output is correct
18 Correct 84 ms 79044 KB Output is correct
19 Correct 84 ms 79044 KB Output is correct
20 Correct 82 ms 79044 KB Output is correct
21 Correct 81 ms 79076 KB Output is correct
22 Correct 82 ms 79076 KB Output is correct
23 Correct 81 ms 79076 KB Output is correct
24 Correct 86 ms 79076 KB Output is correct
25 Correct 88 ms 79076 KB Output is correct
26 Correct 76 ms 79076 KB Output is correct
27 Correct 82 ms 79076 KB Output is correct
28 Correct 82 ms 79076 KB Output is correct
29 Correct 83 ms 79076 KB Output is correct
30 Correct 84 ms 79148 KB Output is correct
31 Correct 84 ms 79148 KB Output is correct
32 Correct 84 ms 79148 KB Output is correct
33 Correct 80 ms 79148 KB Output is correct
34 Correct 84 ms 79148 KB Output is correct
35 Correct 82 ms 79148 KB Output is correct
36 Correct 86 ms 79148 KB Output is correct
37 Correct 88 ms 79148 KB Output is correct
38 Correct 85 ms 79148 KB Output is correct
39 Correct 85 ms 79148 KB Output is correct
40 Correct 86 ms 79148 KB Output is correct
41 Correct 86 ms 79148 KB Output is correct
42 Correct 89 ms 79148 KB Output is correct
43 Correct 81 ms 79148 KB Output is correct
44 Correct 91 ms 79148 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 77916 KB Output is correct
2 Correct 80 ms 78156 KB Output is correct
3 Correct 85 ms 78156 KB Output is correct
4 Correct 94 ms 78288 KB Output is correct
5 Correct 85 ms 78476 KB Output is correct
6 Correct 86 ms 78584 KB Output is correct
7 Correct 86 ms 78584 KB Output is correct
8 Correct 96 ms 78584 KB Output is correct
9 Correct 77 ms 78696 KB Output is correct
10 Correct 77 ms 78696 KB Output is correct
11 Correct 87 ms 78696 KB Output is correct
12 Correct 86 ms 78948 KB Output is correct
13 Correct 88 ms 78948 KB Output is correct
14 Correct 87 ms 78948 KB Output is correct
15 Correct 83 ms 78984 KB Output is correct
16 Correct 88 ms 78992 KB Output is correct
17 Correct 87 ms 78992 KB Output is correct
18 Correct 84 ms 79044 KB Output is correct
19 Correct 84 ms 79044 KB Output is correct
20 Correct 82 ms 79044 KB Output is correct
21 Correct 81 ms 79076 KB Output is correct
22 Correct 82 ms 79076 KB Output is correct
23 Correct 81 ms 79076 KB Output is correct
24 Correct 86 ms 79076 KB Output is correct
25 Correct 88 ms 79076 KB Output is correct
26 Correct 76 ms 79076 KB Output is correct
27 Correct 82 ms 79076 KB Output is correct
28 Correct 82 ms 79076 KB Output is correct
29 Correct 83 ms 79076 KB Output is correct
30 Correct 84 ms 79148 KB Output is correct
31 Correct 84 ms 79148 KB Output is correct
32 Correct 84 ms 79148 KB Output is correct
33 Correct 80 ms 79148 KB Output is correct
34 Correct 84 ms 79148 KB Output is correct
35 Correct 82 ms 79148 KB Output is correct
36 Correct 86 ms 79148 KB Output is correct
37 Correct 88 ms 79148 KB Output is correct
38 Correct 85 ms 79148 KB Output is correct
39 Correct 85 ms 79148 KB Output is correct
40 Correct 86 ms 79148 KB Output is correct
41 Correct 86 ms 79148 KB Output is correct
42 Correct 89 ms 79148 KB Output is correct
43 Correct 81 ms 79148 KB Output is correct
44 Correct 91 ms 79148 KB Output is correct
45 Correct 84 ms 79268 KB Output is correct
46 Correct 91 ms 80308 KB Output is correct
47 Correct 108 ms 80444 KB Output is correct
48 Correct 91 ms 80592 KB Output is correct
49 Correct 83 ms 80592 KB Output is correct
50 Correct 82 ms 80592 KB Output is correct
51 Correct 80 ms 80592 KB Output is correct
52 Correct 95 ms 80876 KB Output is correct
53 Correct 90 ms 81012 KB Output is correct
54 Correct 89 ms 81032 KB Output is correct
55 Correct 89 ms 81108 KB Output is correct
56 Correct 86 ms 81184 KB Output is correct
57 Correct 94 ms 81184 KB Output is correct
58 Correct 96 ms 81184 KB Output is correct
59 Correct 116 ms 81392 KB Output is correct
60 Correct 126 ms 81392 KB Output is correct
61 Correct 91 ms 81592 KB Output is correct
62 Correct 87 ms 81620 KB Output is correct
63 Correct 95 ms 81696 KB Output is correct
64 Correct 92 ms 81696 KB Output is correct
65 Correct 150 ms 81708 KB Output is correct
66 Correct 106 ms 81740 KB Output is correct
67 Correct 92 ms 81792 KB Output is correct
68 Correct 81 ms 81792 KB Output is correct
69 Correct 89 ms 82024 KB Output is correct
70 Correct 91 ms 82124 KB Output is correct
71 Correct 89 ms 82128 KB Output is correct
72 Correct 90 ms 82128 KB Output is correct
73 Correct 102 ms 82128 KB Output is correct
74 Correct 91 ms 82204 KB Output is correct
75 Correct 89 ms 82332 KB Output is correct
76 Correct 91 ms 82332 KB Output is correct
77 Correct 91 ms 82384 KB Output is correct
78 Correct 85 ms 82496 KB Output is correct
79 Correct 89 ms 82496 KB Output is correct
80 Correct 91 ms 82524 KB Output is correct
81 Correct 93 ms 82572 KB Output is correct
82 Correct 96 ms 82636 KB Output is correct
83 Correct 89 ms 82700 KB Output is correct
84 Correct 89 ms 82764 KB Output is correct
85 Correct 91 ms 82812 KB Output is correct
86 Correct 86 ms 82860 KB Output is correct

Subtask #3
84.0 / 84.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 77916 KB Output is correct
2 Correct 80 ms 78156 KB Output is correct
3 Correct 85 ms 78156 KB Output is correct
4 Correct 94 ms 78288 KB Output is correct
5 Correct 85 ms 78476 KB Output is correct
6 Correct 86 ms 78584 KB Output is correct
7 Correct 86 ms 78584 KB Output is correct
8 Correct 96 ms 78584 KB Output is correct
9 Correct 77 ms 78696 KB Output is correct
10 Correct 77 ms 78696 KB Output is correct
11 Correct 87 ms 78696 KB Output is correct
12 Correct 86 ms 78948 KB Output is correct
13 Correct 88 ms 78948 KB Output is correct
14 Correct 87 ms 78948 KB Output is correct
15 Correct 83 ms 78984 KB Output is correct
16 Correct 88 ms 78992 KB Output is correct
17 Correct 87 ms 78992 KB Output is correct
18 Correct 84 ms 79044 KB Output is correct
19 Correct 84 ms 79044 KB Output is correct
20 Correct 82 ms 79044 KB Output is correct
21 Correct 81 ms 79076 KB Output is correct
22 Correct 82 ms 79076 KB Output is correct
23 Correct 81 ms 79076 KB Output is correct
24 Correct 86 ms 79076 KB Output is correct
25 Correct 88 ms 79076 KB Output is correct
26 Correct 76 ms 79076 KB Output is correct
27 Correct 82 ms 79076 KB Output is correct
28 Correct 82 ms 79076 KB Output is correct
29 Correct 83 ms 79076 KB Output is correct
30 Correct 84 ms 79148 KB Output is correct
31 Correct 84 ms 79148 KB Output is correct
32 Correct 84 ms 79148 KB Output is correct
33 Correct 80 ms 79148 KB Output is correct
34 Correct 84 ms 79148 KB Output is correct
35 Correct 82 ms 79148 KB Output is correct
36 Correct 86 ms 79148 KB Output is correct
37 Correct 88 ms 79148 KB Output is correct
38 Correct 85 ms 79148 KB Output is correct
39 Correct 85 ms 79148 KB Output is correct
40 Correct 86 ms 79148 KB Output is correct
41 Correct 86 ms 79148 KB Output is correct
42 Correct 89 ms 79148 KB Output is correct
43 Correct 81 ms 79148 KB Output is correct
44 Correct 91 ms 79148 KB Output is correct
45 Correct 84 ms 79268 KB Output is correct
46 Correct 91 ms 80308 KB Output is correct
47 Correct 108 ms 80444 KB Output is correct
48 Correct 91 ms 80592 KB Output is correct
49 Correct 83 ms 80592 KB Output is correct
50 Correct 82 ms 80592 KB Output is correct
51 Correct 80 ms 80592 KB Output is correct
52 Correct 95 ms 80876 KB Output is correct
53 Correct 90 ms 81012 KB Output is correct
54 Correct 89 ms 81032 KB Output is correct
55 Correct 89 ms 81108 KB Output is correct
56 Correct 86 ms 81184 KB Output is correct
57 Correct 94 ms 81184 KB Output is correct
58 Correct 96 ms 81184 KB Output is correct
59 Correct 116 ms 81392 KB Output is correct
60 Correct 126 ms 81392 KB Output is correct
61 Correct 91 ms 81592 KB Output is correct
62 Correct 87 ms 81620 KB Output is correct
63 Correct 95 ms 81696 KB Output is correct
64 Correct 92 ms 81696 KB Output is correct
65 Correct 150 ms 81708 KB Output is correct
66 Correct 106 ms 81740 KB Output is correct
67 Correct 92 ms 81792 KB Output is correct
68 Correct 81 ms 81792 KB Output is correct
69 Correct 89 ms 82024 KB Output is correct
70 Correct 91 ms 82124 KB Output is correct
71 Correct 89 ms 82128 KB Output is correct
72 Correct 90 ms 82128 KB Output is correct
73 Correct 102 ms 82128 KB Output is correct
74 Correct 91 ms 82204 KB Output is correct
75 Correct 89 ms 82332 KB Output is correct
76 Correct 91 ms 82332 KB Output is correct
77 Correct 91 ms 82384 KB Output is correct
78 Correct 85 ms 82496 KB Output is correct
79 Correct 89 ms 82496 KB Output is correct
80 Correct 91 ms 82524 KB Output is correct
81 Correct 93 ms 82572 KB Output is correct
82 Correct 96 ms 82636 KB Output is correct
83 Correct 89 ms 82700 KB Output is correct
84 Correct 89 ms 82764 KB Output is correct
85 Correct 91 ms 82812 KB Output is correct
86 Correct 86 ms 82860 KB Output is correct
87 Correct 109 ms 84960 KB Output is correct
88 Correct 175 ms 91888 KB Output is correct
89 Correct 458 ms 116220 KB Output is correct
90 Correct 477 ms 118436 KB Output is correct
91 Correct 469 ms 120488 KB Output is correct
92 Correct 180 ms 120488 KB Output is correct
93 Correct 188 ms 120488 KB Output is correct
94 Correct 180 ms 120488 KB Output is correct
95 Correct 248 ms 132652 KB Output is correct
96 Correct 258 ms 134748 KB Output is correct
97 Correct 274 ms 136888 KB Output is correct
98 Correct 267 ms 138976 KB Output is correct
99 Correct 247 ms 139336 KB Output is correct
100 Correct 474 ms 139336 KB Output is correct
101 Correct 550 ms 139336 KB Output is correct
102 Correct 522 ms 139336 KB Output is correct
103 Correct 519 ms 139336 KB Output is correct
104 Correct 265 ms 149656 KB Output is correct
105 Correct 253 ms 151660 KB Output is correct
106 Correct 250 ms 153784 KB Output is correct
107 Correct 437 ms 153784 KB Output is correct
108 Correct 488 ms 154384 KB Output is correct
109 Correct 436 ms 156008 KB Output is correct
110 Correct 180 ms 156008 KB Output is correct
111 Correct 263 ms 163276 KB Output is correct
112 Correct 248 ms 164596 KB Output is correct
113 Correct 242 ms 164596 KB Output is correct
114 Correct 512 ms 164596 KB Output is correct
115 Correct 598 ms 164596 KB Output is correct
116 Correct 339 ms 169304 KB Output is correct
117 Correct 325 ms 170024 KB Output is correct
118 Correct 288 ms 171320 KB Output is correct
119 Correct 304 ms 172888 KB Output is correct
120 Correct 292 ms 174984 KB Output is correct
121 Correct 338 ms 176288 KB Output is correct
122 Correct 300 ms 177516 KB Output is correct
123 Correct 365 ms 180140 KB Output is correct
124 Correct 281 ms 181440 KB Output is correct
125 Correct 291 ms 183072 KB Output is correct
126 Correct 264 ms 185168 KB Output is correct
127 Correct 273 ms 186300 KB Output is correct
128 Correct 281 ms 187804 KB Output is correct