oj.uz

Submission #572150

# Submission time Handle Problem Language Result Execution time Memory
572150 2022-06-03T19:14:19 Z MohammadAghil Jail (JOI22_jail) C++14
21 / 100
 5000 ms 12748 KB 
      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

vector<int> adj[maxn];
bool is[maxn];

bool dfs(int r, int g, int p = -1, int cr = 0){
     cr += is[r];
     if(r == g) return cr <= 1;
     for(int c: adj[r]) if(c - p && !dfs(c, g, r, cr)) return false;
     return true; 
}

void solve(){
     int n; cin >> n;
     rep(i,0,n) adj[i].clear();
     rep(i,1,n) {
          int u, v; cin >> u >> v; u--, v--;
          adj[u].pb(v), adj[v].pb(u);
     }
     int m; cin >> m;
     vector<int> s(m), t(m);
     rep(i,0,m) cin >> s[i] >> t[i], s[i]--, t[i]--;
     vector<int> id(m); iota(all(id), 0);
     do{
          fill(is, is + n, false);
          rep(i,0,m) is[s[i]] = true;
          bool ok = true;
          rep(i,0,m){
               if(!dfs(s[id[i]], t[id[i]])){
                    ok = false;
                    break;
               }
               is[s[id[i]]] = false, is[t[id[i]]] = true;
          }  
          if(ok){
               cout << "Yes\n";
               return;
          }
     }while(next_permutation(all(id)));
     cout << "No\n";
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     int t; cin >> t;
     while(t--) solve();
     return 0; 
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 15 ms 12380 KB Output is correct
5 Correct 25 ms 12748 KB Output is correct
6 Correct 7 ms 12080 KB Output is correct
7 Correct 23 ms 12116 KB Output is correct
8 Execution timed out 5047 ms 12116 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12068 KB Output is correct
2 Correct 8 ms 11956 KB Output is correct
3 Correct 7 ms 12084 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 8 ms 12084 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 8 ms 12084 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 8 ms 12080 KB Output is correct
11 Correct 7 ms 12104 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12068 KB Output is correct
2 Correct 8 ms 11956 KB Output is correct
3 Correct 7 ms 12084 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 8 ms 12084 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 8 ms 12084 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 8 ms 12080 KB Output is correct
11 Correct 7 ms 12104 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 12072 KB Output is correct
16 Correct 23 ms 12116 KB Output is correct
17 Correct 8 ms 12100 KB Output is correct
18 Correct 25 ms 12000 KB Output is correct
19 Correct 7 ms 11988 KB Output is correct
20 Correct 20 ms 12080 KB Output is correct
21 Correct 30 ms 12016 KB Output is correct
22 Correct 17 ms 12120 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 8 ms 11988 KB Output is correct
25 Correct 68 ms 12092 KB Output is correct
26 Correct 14 ms 11988 KB Output is correct
27 Correct 15 ms 12216 KB Output is correct
28 Correct 14 ms 11988 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12068 KB Output is correct
2 Correct 8 ms 11956 KB Output is correct
3 Correct 7 ms 12084 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 8 ms 12084 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 8 ms 12084 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 8 ms 12080 KB Output is correct
11 Correct 7 ms 12104 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 12072 KB Output is correct
16 Correct 23 ms 12116 KB Output is correct
17 Correct 8 ms 12100 KB Output is correct
18 Correct 25 ms 12000 KB Output is correct
19 Correct 7 ms 11988 KB Output is correct
20 Correct 20 ms 12080 KB Output is correct
21 Correct 30 ms 12016 KB Output is correct
22 Correct 17 ms 12120 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 8 ms 11988 KB Output is correct
25 Correct 68 ms 12092 KB Output is correct
26 Correct 14 ms 11988 KB Output is correct
27 Correct 15 ms 12216 KB Output is correct
28 Correct 14 ms 11988 KB Output is correct
29 Execution timed out 5027 ms 12084 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12068 KB Output is correct
2 Correct 8 ms 11956 KB Output is correct
3 Correct 7 ms 12084 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 8 ms 12084 KB Output is correct
6 Correct 8 ms 12116 KB Output is correct
7 Correct 8 ms 12084 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 8 ms 12080 KB Output is correct
11 Correct 7 ms 12104 KB Output is correct
12 Correct 7 ms 11988 KB Output is correct
13 Correct 7 ms 11988 KB Output is correct
14 Correct 8 ms 11988 KB Output is correct
15 Correct 7 ms 12072 KB Output is correct
16 Correct 23 ms 12116 KB Output is correct
17 Correct 8 ms 12100 KB Output is correct
18 Correct 25 ms 12000 KB Output is correct
19 Correct 7 ms 11988 KB Output is correct
20 Correct 20 ms 12080 KB Output is correct
21 Correct 30 ms 12016 KB Output is correct
22 Correct 17 ms 12120 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 8 ms 11988 KB Output is correct
25 Correct 68 ms 12092 KB Output is correct
26 Correct 14 ms 11988 KB Output is correct
27 Correct 15 ms 12216 KB Output is correct
28 Correct 14 ms 11988 KB Output is correct
29 Execution timed out 5027 ms 12084 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Execution timed out 5060 ms 12192 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 15 ms 12380 KB Output is correct
5 Correct 25 ms 12748 KB Output is correct
6 Correct 7 ms 12080 KB Output is correct
7 Correct 23 ms 12116 KB Output is correct
8 Execution timed out 5047 ms 12116 KB Time limit exceeded
9 Halted 0 ms 0 KB -