oj.uz

Submission #710106

# Submission time Handle Problem Language Result Execution time Memory
710106 2023-03-15T04:42:31 Z nicky4321 Jail (JOI22_jail) C++14
5 / 100
 57 ms 74256 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
vi edge[MAX], p[MAX], e[MAX];
int cnt[MAX], u[MAX], v[MAX], from[MAX], vis[MAX];

bool dfs(int now){
    vis[now] = 1;
    for(int i : e[now]){
        if(vis[i]){
            return 1;
        }
        if(dfs(i))
            return 1;
    }
    return 0;
}

void solve(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        p[i].clear();
        edge[i].clear();
        e[i].clear();
    }
    for(int i = 1;i < n;i++){
        int u, v;
        cin >> u >> v;
        edge[u].PB(v);
        edge[v].PB(u);
    }
    int m;
    cin >> m;
    for(int i = 1;i <= m;i++){
        cin >> u[i] >> v[i];
        p[u[i]].PB(i);
        p[v[i]].PB(-i);
    }
    map<pii, int> mp;
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= n;j++)
            vis[j] = cnt[j] = 0;
        queue<int> q;
        q.push(u[i]);
        while(!q.empty()){
            int now = q.front();
            q.pop();
            for(int i : edge[now]){
                if(!vis[i]){
                    vis[i] = 1;
                    from[i] = now;
                    q.push(i);
                }
            }
        }
        int tmp = v[i];
        while(tmp != u[i]){
            for(int j : p[tmp]){
                if(abs(j) == i)
                    continue;
                if(j < 0 && !mp.count(MP(-j, i))){
                    e[-j].PB(i);
                    mp[MP(-j, i)] = 1;
                }else if(j > 0 && !mp.count(MP(i, j))){
                    e[i].PB(j);
                    mp[MP(i, j)] = 1;
                }
            }
            tmp = from[tmp];
        }
        for(int j : p[tmp]){
            if(abs(j) == i)
                continue;
            if(j < 0 && !mp.count(MP(-j, i))){
                e[-j].PB(i);
                mp[MP(-j, i)] = 1;
            }else if(j > 0 && !mp.count(MP(i, j))){
                e[i].PB(j);
                mp[MP(i, j)] = 1;
            }
        }
    }
    for(int i = 1;i <= m;i++){
        for(int j = 1;j <= m;j++)
            vis[j] = 0;
        if(dfs(i)){
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}

int main(){
    IOS
    CASE
        solve();
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 74160 KB Output is correct
2 Incorrect 44 ms 74112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 74184 KB Output is correct
2 Correct 36 ms 74200 KB Output is correct
3 Correct 37 ms 74200 KB Output is correct
4 Correct 36 ms 74212 KB Output is correct
5 Correct 41 ms 74236 KB Output is correct
6 Correct 50 ms 74256 KB Output is correct
7 Correct 36 ms 74196 KB Output is correct
8 Correct 57 ms 74232 KB Output is correct
9 Correct 40 ms 74192 KB Output is correct
10 Correct 36 ms 74248 KB Output is correct
11 Correct 36 ms 74144 KB Output is correct
12 Correct 38 ms 74244 KB Output is correct
13 Correct 45 ms 74144 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 74184 KB Output is correct
2 Correct 36 ms 74200 KB Output is correct
3 Correct 37 ms 74200 KB Output is correct
4 Correct 36 ms 74212 KB Output is correct
5 Correct 41 ms 74236 KB Output is correct
6 Correct 50 ms 74256 KB Output is correct
7 Correct 36 ms 74196 KB Output is correct
8 Correct 57 ms 74232 KB Output is correct
9 Correct 40 ms 74192 KB Output is correct
10 Correct 36 ms 74248 KB Output is correct
11 Correct 36 ms 74144 KB Output is correct
12 Correct 38 ms 74244 KB Output is correct
13 Correct 45 ms 74144 KB Output is correct
14 Correct 38 ms 74208 KB Output is correct
15 Incorrect 41 ms 74132 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 74184 KB Output is correct
2 Correct 36 ms 74200 KB Output is correct
3 Correct 37 ms 74200 KB Output is correct
4 Correct 36 ms 74212 KB Output is correct
5 Correct 41 ms 74236 KB Output is correct
6 Correct 50 ms 74256 KB Output is correct
7 Correct 36 ms 74196 KB Output is correct
8 Correct 57 ms 74232 KB Output is correct
9 Correct 40 ms 74192 KB Output is correct
10 Correct 36 ms 74248 KB Output is correct
11 Correct 36 ms 74144 KB Output is correct
12 Correct 38 ms 74244 KB Output is correct
13 Correct 45 ms 74144 KB Output is correct
14 Correct 38 ms 74208 KB Output is correct
15 Incorrect 41 ms 74132 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 74184 KB Output is correct
2 Correct 36 ms 74200 KB Output is correct
3 Correct 37 ms 74200 KB Output is correct
4 Correct 36 ms 74212 KB Output is correct
5 Correct 41 ms 74236 KB Output is correct
6 Correct 50 ms 74256 KB Output is correct
7 Correct 36 ms 74196 KB Output is correct
8 Correct 57 ms 74232 KB Output is correct
9 Correct 40 ms 74192 KB Output is correct
10 Correct 36 ms 74248 KB Output is correct
11 Correct 36 ms 74144 KB Output is correct
12 Correct 38 ms 74244 KB Output is correct
13 Correct 45 ms 74144 KB Output is correct
14 Correct 38 ms 74208 KB Output is correct
15 Incorrect 41 ms 74132 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 74168 KB Output is correct
2 Correct 47 ms 74176 KB Output is correct
3 Incorrect 37 ms 74188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 74160 KB Output is correct
2 Incorrect 44 ms 74112 KB Output isn't correct
3 Halted 0 ms 0 KB -