Submission #427788

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
427788	2021-06-14 22:41:42	Pajaraja	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1110 ms	49876 KiB

meetings2

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 <bits/stdc++.h>
#define MAXN 200007
#define MAXL 20
using namespace std;
vector<int> g[MAXN],v[MAXN];
int p[MAXL][MAXN],d[MAXN],n,ans[MAXN],c,in[MAXN],out[MAXN],t;
int dfsc(int s,int f,int dub)
{
    p[0][s]=f;
    in[s]=t++;
    d[s]=dub;
    bool centroid=true;
    int sum=1;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f)
    {
        int a=dfsc(g[s][i],s,dub+1);
        if(a>n/2) centroid=false;
        sum+=a;
    }
    if(n-sum>n/2) centroid=false;
    if(centroid) c=s;
    out[s]=t++;
    return sum;
}
bool insub(int u,int v) {return in[u]>=in[v] && out[u]<=out[v];}
int lca(int u,int v)
{
    if(insub(u,v)) return v;
    if(insub(v,u)) return u;
    for(int i=MAXL-1;i>=0;i--) if(!insub(v,p[i][u])) u=p[i][u];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

meetings2.cpp: In function 'int dfsc(int, int, int)':
meetings2.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f)
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'int dfs(int, int)':
meetings2.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) sum+=dfs(g[s][i],s);
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80