oj.uz

Submission #702458

# Submission time Handle Problem Language Result Execution time Memory
702458 2023-02-24T06:19:36 Z MinhAnhnd Jail (JOI22_jail) C++14
21 / 100
 5000 ms 624 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define ll unsigned long long

using namespace __gnu_pbds;

#define modu 1000000007
#define sizeofA 1201
int sum(ll a,ll b){
	return ((a % modu) + (b % modu))% modu;
}

typedef tree<long,null_type,less<long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

long max_ = 0;
ordered_set higher;
long N,M;
vector<long> adj[sizeofA];
vector<long> hyper_adj[sizeofA];
bool the_path[sizeofA] = {};
bool filling[sizeofA] = {};
//hyper_adj[a] -> b then (a before b)
bool check_valid(long now){
    if(the_path[now]){return 0;}

    the_path[now] = 1;
    filling[now] = 1;

    for (auto godo: hyper_adj[now]){
        //cout<<godo<<" "<<now<<endl;
        if(!check_valid(godo)){
            the_path[now] = 0;
            return 0;
        }
    }


    the_path[now] = 0;
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0);
    ll t;
    cin>>t;
    while(t--){
    cin>>N;
    //memset(the_path, 0, sizeof(the_path));
    memset(filling, 0, sizeof(N+1));
    for(long i = 1;i<=N+1;i++){
        adj[i].clear();
        hyper_adj[i].clear();
    }
    long start[N+1]={};
    long work[N+1] ={};

    for(long i = 1;i<=N-1;i++){
        long temp1, temp2;
        cin>>temp1>>temp2;
        adj[temp1].push_back(temp2);
        adj[temp2].push_back(temp1);
    }
    cin>>M;
    for (long i = 1;i<=M;i++){
        long temp1, temp2;
        cin>>temp1>>temp2;
        start[temp1]=i;
        work[temp2]=i;
    }
    vector<long> children[sizeofA];
    long father[sizeofA]={};
    stack<long> tovisit;
    stack<long> dfs;

    bool visited[sizeofA] = {};
    dfs.push(1);
    while(!dfs.empty()){
        long current_node = dfs.top();
        dfs.pop();
        visited[current_node] = 1;
        tovisit.push(current_node);
        for (auto togo : adj[current_node]){
            if (!visited[togo]){
                father[togo] = current_node;
                children[current_node].push_back(togo);
                dfs.push(togo);
            }
        }
    }
    multiset<long> beg[sizeofA];
    stack<long> to_remove;
    while(!tovisit.empty()){
        long current_node = tovisit.top();

        for(auto child : children[current_node]){
            if (beg[current_node].size() < beg[child].size()) {
				swap(beg[current_node], beg[child]);
			}
			for (auto item : beg[child]) {
                beg[current_node].insert(item);
                to_remove.push(item);
            }
        }

        if(start[current_node]!=0){
            long begin_ = start[current_node];
            for(auto item: beg[current_node]){
                if (begin_ !=item) hyper_adj[begin_].push_back(item);
            }
        }

        if(work[current_node]!=0){
            long end_ = work[current_node];
            for(auto item: beg[current_node]){
                if(end_ != item) hyper_adj[item].push_back(end_);
            }
        }

        if((start[current_node]>0)&&(work[current_node]>0)){
            hyper_adj[start[current_node]].push_back(work[current_node]);
        }

        if(start[current_node]!=0){
            beg[current_node].insert(start[current_node]);
            to_remove.push(start[current_node]);
        }
        if(work[current_node]!=0){
            beg[current_node].insert(work[current_node]);
            to_remove.push(work[current_node]);
        }


        while(!to_remove.empty()){
            auto it = to_remove.top();
            auto counter = beg[current_node].count(it);
            if (counter > 1) beg[current_node].erase(it);
            to_remove.pop();
            //cout<<it<<" "<<counter<<endl;
        }

        tovisit.pop();
        //cout<<current_node<<" "<<beg[current_node].size()<<endl;
        //cout<<current_node<<" "<<start[current_node]<<" "<<work[current_node]<<endl;
    }
    bool checking = 1;
    for (long i = 1;i<=N;i++){
        if(!filling[i]){
            checking = checking & check_valid(i);
            if (checking == 0){
                break;
            }
        }
    }

    if (checking){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    }
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:76:10: warning: variable 'father' set but not used [-Wunused-but-set-variable]
   76 |     long father[sizeofA]={};
      |          ^~~~~~

Subtask #1
0 / 5.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 1 ms 340 KB Output is correct
4 Correct 12 ms 468 KB Output is correct
5 Correct 25 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Execution timed out 5090 ms 468 KB Time limit exceeded
9 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 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 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 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 28.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 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Execution timed out 5057 ms 468 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.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 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Execution timed out 5057 ms 468 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
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 12 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 484 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Incorrect 54 ms 624 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.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 1 ms 340 KB Output is correct
4 Correct 12 ms 468 KB Output is correct
5 Correct 25 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Execution timed out 5090 ms 468 KB Time limit exceeded
9 Halted 0 ms 0 KB -