oj.uz

Submission #814732

# Submission time Handle Problem Language Result Execution time Memory
814732 2023-08-08T09:24:03 Z groshi Jail (JOI22_jail) C++17
72 / 100
 4121 ms 1048576 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct wi{
    vector<int> Q;
    int skoki[20];
    int poziom=0;
    vector<int> po;
    int przed=0;
}*w;
int pocz[130000];
int kon[130000];
int mam[130000][2];
void pusc(int x)
{
    int gdzie=0;
    while(w[w[x].skoki[gdzie]].skoki[gdzie]!=0)
    {
        w[x].skoki[gdzie+1]=w[w[x].skoki[gdzie]].skoki[gdzie];
        gdzie++;
    }
}
void dfs(int x,int ojc)
{
    w[x].poziom=w[ojc].poziom+1;
    for(int i=0;i<w[x].Q.size();i++)
    {
        int pom=w[x].Q[i];
        if(pom==ojc)
        continue;
        w[pom].skoki[0]=x;
        pusc(pom);
        dfs(pom,x);
    }
}
int lca(int x,int y)
{
    if(w[x].poziom>w[y].poziom)
        swap(x,y);
    for(int i=19;i>=0;i--)
        if(w[w[y].skoki[i]].poziom>=w[x].poziom)
            y=w[y].skoki[i];
    if(x==y)
        return x;
    for(int i=19;i>=0;i--)
        if(w[x].skoki[i]!=w[y].skoki[i])
            x=w[x].skoki[i],y=w[y].skoki[i];
    return w[x].skoki[0];
}
void lec(int x,int y,int kto)
{
    while(x!=y)
    {
        if(pocz[x]!=0 && pocz[x]!=kto)
        {
            w[kto].przed++;
            w[pocz[x]].po.push_back(kto);
        }
        if(kon[x]!=0 && kon[x]!=kto)
        {
            w[kto].po.push_back(kon[x]);
            w[kon[x]].przed++;
        }
        x=w[x].skoki[0];
    }
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int zap;
    cin>>zap;
    while(zap--)
    {
        int n,x,y;
        cin>>n;
        for(int i=1;i<=n;i++)
            pocz[i]=0,kon[i]=0;
        w=new wi[n+3];
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            w[x].Q.push_back(y);
            w[y].Q.push_back(x);
        }
        dfs(1,0);
        int m;
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            pocz[x]=i;
            kon[y]=i;
            mam[i][0]=x;
            mam[i][1]=y;
        }
        for(int i=1;i<=m;i++)
        {
            x=mam[i][0];
            y=mam[i][1];
            int lcaa=lca(x,y);
            lec(x,lcaa,i);
            lec(y,lcaa,i);
            if(pocz[lcaa]!=0 && pocz[lcaa]!=i)
            {
                w[i].przed++;
                w[pocz[lcaa]].po.push_back(i);
            }
            if(kon[lcaa]!=0 && kon[lcaa]!=i)
            {
                w[i].po.push_back(kon[lcaa]);
                w[kon[lcaa]].przed++;
            }
        }
        int ilu=0;
        vector<int> mam;
        for(int i=1;i<=m;i++)
            if(w[i].przed==0)
                mam.push_back(i);
        while(mam.size())
        {
            int x=mam.back();
            mam.pop_back();
            ilu++;
            for(int i=0;i<w[x].po.size();i++)
            {
                w[w[x].po[i]].przed--;
                if(w[w[x].po[i]].przed==0)
                    mam.push_back(w[x].po[i]);
            }
        }
        if(ilu==m)
            cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

Compilation message

jail.cpp: In function 'void dfs(long long int, long long int)':
jail.cpp:26:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<w[x].Q.size();i++)
      |                 ~^~~~~~~~~~~~~~
jail.cpp: In function 'int32_t main()':
jail.cpp:126:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |             for(int i=0;i<w[x].po.size();i++)
      |                         ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 17 ms 14492 KB Output is correct
5 Correct 34 ms 31136 KB Output is correct
6 Correct 2 ms 1520 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 3 ms 2260 KB Output is correct
9 Correct 109 ms 48488 KB Output is correct
10 Correct 674 ms 40560 KB Output is correct
11 Correct 9 ms 6628 KB Output is correct
12 Correct 60 ms 43972 KB Output is correct
13 Correct 181 ms 97348 KB Output is correct
14 Correct 204 ms 126912 KB Output is correct
15 Runtime error 4121 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1624 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 2 ms 1592 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1624 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 2 ms 1592 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 2 ms 1620 KB Output is correct
17 Correct 2 ms 1620 KB Output is correct
18 Correct 2 ms 1620 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 1620 KB Output is correct
21 Correct 2 ms 1620 KB Output is correct
22 Correct 2 ms 1604 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 1620 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 ms 1620 KB Output is correct
28 Correct 1 ms 468 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1624 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 2 ms 1592 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 2 ms 1620 KB Output is correct
17 Correct 2 ms 1620 KB Output is correct
18 Correct 2 ms 1620 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 1620 KB Output is correct
21 Correct 2 ms 1620 KB Output is correct
22 Correct 2 ms 1604 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 1620 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 ms 1620 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 3 ms 2324 KB Output is correct
30 Correct 3 ms 1732 KB Output is correct
31 Correct 3 ms 1876 KB Output is correct
32 Correct 2 ms 1672 KB Output is correct
33 Correct 2 ms 1624 KB Output is correct
34 Correct 2 ms 1620 KB Output is correct
35 Correct 4 ms 2516 KB Output is correct
36 Correct 3 ms 1236 KB Output is correct
37 Correct 2 ms 904 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1624 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct
9 Correct 2 ms 1592 KB Output is correct
10 Correct 2 ms 1620 KB Output is correct
11 Correct 2 ms 1364 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 2 ms 1620 KB Output is correct
17 Correct 2 ms 1620 KB Output is correct
18 Correct 2 ms 1620 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 1620 KB Output is correct
21 Correct 2 ms 1620 KB Output is correct
22 Correct 2 ms 1604 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 2 ms 1620 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 ms 1620 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 3 ms 2324 KB Output is correct
30 Correct 3 ms 1732 KB Output is correct
31 Correct 3 ms 1876 KB Output is correct
32 Correct 2 ms 1672 KB Output is correct
33 Correct 2 ms 1624 KB Output is correct
34 Correct 2 ms 1620 KB Output is correct
35 Correct 4 ms 2516 KB Output is correct
36 Correct 3 ms 1236 KB Output is correct
37 Correct 2 ms 904 KB Output is correct
38 Correct 100 ms 49712 KB Output is correct
39 Correct 600 ms 42024 KB Output is correct
40 Correct 70 ms 40812 KB Output is correct
41 Correct 39 ms 32584 KB Output is correct
42 Correct 55 ms 39772 KB Output is correct
43 Correct 44 ms 32188 KB Output is correct
44 Correct 11 ms 7124 KB Output is correct
45 Correct 66 ms 34268 KB Output is correct
46 Correct 61 ms 34188 KB Output is correct
47 Correct 201 ms 36996 KB Output is correct
48 Correct 213 ms 37016 KB Output is correct
49 Correct 69 ms 34420 KB Output is correct
50 Correct 71 ms 34380 KB Output is correct
51 Correct 61 ms 35148 KB Output is correct
52 Correct 53 ms 35076 KB Output is correct
53 Correct 12 ms 8276 KB Output is correct
54 Correct 80 ms 34884 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 6632 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 2 ms 1312 KB Output is correct
13 Correct 33 ms 20924 KB Output is correct
14 Correct 44 ms 33144 KB Output is correct
15 Correct 40 ms 27140 KB Output is correct
16 Correct 76 ms 35132 KB Output is correct
17 Correct 154 ms 45520 KB Output is correct
18 Correct 341 ms 83204 KB Output is correct
19 Correct 79 ms 35468 KB Output is correct
20 Correct 81 ms 35444 KB Output is correct
21 Correct 83 ms 35420 KB Output is correct
22 Correct 131 ms 46672 KB Output is correct
23 Correct 126 ms 47520 KB Output is correct
24 Correct 126 ms 46728 KB Output is correct
25 Correct 126 ms 46952 KB Output is correct
26 Correct 123 ms 46788 KB Output is correct
27 Correct 189 ms 41828 KB Output is correct
28 Correct 144 ms 41588 KB Output is correct
29 Correct 153 ms 41624 KB Output is correct
30 Correct 123 ms 37652 KB Output is correct
31 Correct 123 ms 37648 KB Output is correct
32 Correct 120 ms 37652 KB Output is correct
33 Correct 112 ms 37736 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 17 ms 14492 KB Output is correct
5 Correct 34 ms 31136 KB Output is correct
6 Correct 2 ms 1520 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 3 ms 2260 KB Output is correct
9 Correct 109 ms 48488 KB Output is correct
10 Correct 674 ms 40560 KB Output is correct
11 Correct 9 ms 6628 KB Output is correct
12 Correct 60 ms 43972 KB Output is correct
13 Correct 181 ms 97348 KB Output is correct
14 Correct 204 ms 126912 KB Output is correct
15 Runtime error 4121 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -