Submission #1082511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082511		vjudge1	Construction of Highway (JOI18_construction)	C++17	7 / 100	2041 ms	604 KiB

construction

#include<bits/stdc++.h>
#define INF 1e18
#define fi first
#define se second
#define FOR(i, k, n) for(ll i = k; i <= n; i++)
#define FOR1(i, k, n) for(ll i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "BAI1.inp"
#define output "BAI1.out"
#define rf 	freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int base = 29;
void add(int &a, int b) 
{
	a += b; 
	if(a >= mod) a -= mod; 
	if(a < 0) a += mod; 
}
int par[maxn];
int a[maxn];
int main()
{
	fastio;
	int n;
	cin >> n;
	FOR(i, 1, n)
		cin >> a[i];
	FOR(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		vi vv;
		par[v] = u;
		while(u != 1)
		{
			vv.pb(u);
			u = par[u];
		}
		vv.pb(1);
		reverse(vv.begin(), vv.end());
		if(vv.size() == 1)
			cout << "0\n";
		else
		{
			int cnt = 0;
			FOR(i, 0, vv.size() - 2)
				FOR(j, i + 1, vv.size() - 1)
					if(a[vv[j]] < a[vv[i]])
						cnt++;
			cout << cnt << "\n";
		}
		for(auto x : vv)
			a[x] = a[v];
	}
	re;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:5:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, k, n) for(ll i = k; i <= n; i++)
......
   57 |    FOR(i, 0, vv.size() - 2)
      |        ~~~~~~~~~~~~~~~~~~~            
construction.cpp:57:4: note: in expansion of macro 'FOR'
   57 |    FOR(i, 0, vv.size() - 2)
      |    ^~~
construction.cpp:5:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, k, n) for(ll i = k; i <= n; i++)
......
   58 |     FOR(j, i + 1, vv.size() - 1)
      |         ~~~~~~~~~~~~~~~~~~~~~~~       
construction.cpp:58:5: note: in expansion of macro 'FOR'
   58 |     FOR(j, i + 1, vv.size() - 1)
      |     ^~~

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