Submission #915075

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
915075	2024-01-23 09:57:30	yellowtoad	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	220 ms	39576 KiB

election_campaign

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;
 
int n, m, p[100010][20], d[100010], sub[100010], dp[100010];
pair<int,int> group[100010];
vector<int> edge[100010];
vector<pair<pair<int,int>,int>> add[100010];
vector<vector<int>> grp, ps, pss;
 
void dfs1(int u, int v, int depth) {
  p[u][0] = v;
  d[u] = depth;
  sub[u] = 1;
  for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs1(edge[u][i],u,depth+1), sub[u] += sub[edge[u][i]];
}
 
int lca(int u, int v) {
  if (d[u] < d[v]) swap(u,v);
  int i = 19;
  while (i >= 0) {
    if (d[p[u][i]] >= d[v]) u = p[u][i];
    i--;
  }
  if (u == v) return u;
  i = 19;
  while (i >= 0) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs1(int, int, int)':
election_campaign.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs1(edge[u][i],u,depth+1), sub[u] += sub[edge[u][i]];
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void hld(int, int, int)':
election_campaign.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) hld(edge[u][i],u,(sub[edge[u][i]] <= (sub[u]-1)/2));
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i = 0; i < edge[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i = 0; i < add[u].size(); i++) dp[u] = max(dp[u],add[u][i].s+sum(add[u][i].f.f,u)-summ(add[u][i].f.f,u)+sum(add[u][i].f.s,u)-summ(add[u][i].f.s,u)-tmp);
      |                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40