Submission #163882

#	Time	Username	Problem	Language	Result	Execution time	Memory
163882		arnold518	Construction of Highway (JOI18_construction)	C++14	16 / 100	2061 ms	10764 KiB

construction

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, C[MAXN+10], A[MAXN+10], B[MAXN+10];
vector<int> adj[MAXN+10];
vector<int> comp;

int par[MAXN+10];

void dfs(int now, int bef)
{
	par[now]=bef;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now);
	}
}

struct BIT
{
	vector<int> tree;
	BIT() : tree(N+10) {}
	void update(int i) { for(; i<=N; i+=(i&-i)) tree[i]++; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
};

int main()
{
	int i, j;

	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%d", &C[i]), comp.push_back(C[i]);
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for(i=1; i<=N; i++) C[i]=lower_bound(comp.begin(), comp.end(), C[i])-comp.begin()+1;
	
	for(i=1; i<N; i++) 
	{
		scanf("%d%d", &A[i], &B[i]);
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(1, 1);

	for(j=1; j<N; j++)
	{
		vector<int> V;
		int now=A[j];
		while(now!=1) V.push_back(now), now=par[now];
		V.push_back(1);

		BIT bit;
		ll ans=0;
		for(i=0; i<V.size(); i++)
		{
			ans+=bit.query(C[V[i]]-1);
			bit.update(C[V[i]]);
		}
		printf("%lld\n", ans);

		for(i=0; i<V.size(); i++) C[V[i]]=C[B[j]];
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:61:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<V.size(); i++)
            ~^~~~~~~~~
construction.cpp:68:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0; i<V.size(); i++) C[V[i]]=C[B[j]];
            ~^~~~~~~~~
construction.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
construction.cpp:39:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &C[i]), comp.push_back(C[i]);
                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84