Submission #643372

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
643372	2022-09-21 22:33:22	Pajaraja	Jail (JOI22_jail)	C++17	100 / 100	1590 ms	359420 KiB

jail

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 120007
#define MAXL 19
using namespace std;
vector<int> g[MAXN],v[3*MAXL*MAXN];
int p[MAXL][MAXN],ind[2][MAXL][MAXN],in[MAXN],out[MAXN],t,deg[MAXN];
void dfs(int s,int f)
{
    p[0][s]=f;
    in[s]=++t;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
    out[s]=t;
}
bool insub(int uu,int vv) {return in[uu]<=in[vv] && out[uu]>=out[vv];} //Jel v insub u
int oneunder(int uu,int vv)
{
    for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][uu],vv)) uu=p[i][uu];
    return uu;
}
int lca(int uu,int vv)
{
    if(insub(uu,vv)) return uu;
    if(insub(vv,uu)) return vv;
    return p[0][oneunder(uu,vv)];
}
void dostuff(int uu,int vv,int type,int br)
{
    for(int i=MAXL-1;i>=0;i--) if(!insub(p[i][uu],vv))
    {
        if(type==0) v[br].push_back(ind[0][i][uu]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

jail.cpp: In function 'void dfs(int, int)':
jail.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:99:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int i=1;i<=c;i++) for(int j=0;j<v[i].size();j++) deg[v[i][j]]++;
      |                                           ~^~~~~~~~~~~~
jail.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for(int i=0;i<v[s].size();i++) {deg[v[s][i]]--; if(deg[v[s][i]]==0) q.push(v[s][i]);}
      |                         ~^~~~~~~~~~~~
jail.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
jail.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
jail.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |             scanf("%d %d",&t1,&t2);
      |             ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
jail.cpp:75:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |             scanf("%d%d",&s,&e);
      |             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23