oj.uz

Submission #985832

# Submission time Handle Problem Language Result Execution time Memory
985832 2024-05-19T04:04:43 Z hengliao File Paths (BOI15_fil) C++17
100 / 100
 139 ms 58248 KB 
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef int ll;

const ll mxN=3005;

vll adj[mxN]; 
ll dis[mxN]; 
ll lef[mxN];
ll rig[mxN];
ll p[2*mxN];
ll l[2*mxN];
vll mul[mxN]; //144
vll add[mxN]; // 144
bool ans[2*mxN]; // 16
ll cnt[1000005];  //16
ll cnt2[1000005]; //16
ll timer=0;

ll n, m, k, s;

void builddis(ll cur, ll d){
    if(cur>n) return;
    dis[cur]=d;
    lef[cur]=timer;
    timer++;
    for(auto &chd:adj[cur]){
        builddis(chd, d+l[chd]+1);
    }
    rig[cur]=timer;
}

bool under(ll a, ll b){
    return lef[a]>=lef[b] && rig[a]<=rig[b];
}

void addedge(ll a, ll b){
    if(under(a, b)){
        mul[b].pb(dis[a]-dis[b]+s+1);
    }
    else{
        ll newdis=dis[a]+s+1;
        ll dif=newdis-dis[b];
        if(dif>0){
            add[b].pb(dif);
        }
    }
}

void dfs(ll cur, ll d){
    if(cur>n){
        ll need=k-d;
        if(need==0){
            ans[cur]=1;
            return;
        }
        if(cnt[need]){
            ans[cur]=1;
            return;
        }
        for(ll i=1;i*i<=need;i++){
            if(need%i==0){
                if(cnt2[i] || cnt2[need/i]){
                    ans[cur]=1;
                    return;
                }
            }
        }
        ans[cur]=0;
        return;
    }
    for(auto &it:add[cur]){
        if(it<1000005) cnt[it]++;
    }
    for(auto &it:mul[cur]){
        if(it<1000005) cnt2[it]++;
    }
    for(auto &chd:adj[cur]){
        dfs(chd, d+l[chd]+1);
    }
    for(auto &it:add[cur]){
        if(it<1000005) cnt[it]--;
    }
    for(auto &it:mul[cur]){
        if(it<1000005) cnt2[it]--;
    }
}

void solve(){
	memset(dis, -1, sizeof(dis));
    cin>>n>>m>>k>>s;
    l[0]=0;
    for(ll i=1;i<=n;i++){
        cin>>p[i]>>l[i];
        adj[p[i]].pb(i);
    }
    for(ll i=n+1;i<=n+m;i++){
        cin>>p[i]>>l[i];
        adj[p[i]].pb(i);
    }
    builddis(0, 0);

    for(ll i=0;i<=n;i++){
        for(ll j=0;j<=n;j++){
            addedge(i, j);
        }
    }

    dfs(0, 0);

    for(ll i=n+1;i<=n+m;i++){
        if(ans[i]){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }    
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();
	return 0;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 4 ms 7772 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 5 ms 9308 KB Output is correct
6 Correct 6 ms 9304 KB Output is correct
7 Correct 5 ms 9320 KB Output is correct
8 Correct 5 ms 9052 KB Output is correct
9 Correct 5 ms 9052 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 3 ms 3252 KB Output is correct
12 Correct 2 ms 3416 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 37968 KB Output is correct
2 Correct 107 ms 39408 KB Output is correct
3 Correct 102 ms 35408 KB Output is correct
4 Correct 111 ms 36828 KB Output is correct
5 Correct 84 ms 41044 KB Output is correct
6 Correct 78 ms 34388 KB Output is correct
7 Correct 109 ms 42888 KB Output is correct
8 Correct 91 ms 37080 KB Output is correct
9 Correct 117 ms 45648 KB Output is correct
10 Correct 129 ms 57956 KB Output is correct
11 Correct 63 ms 24464 KB Output is correct
12 Correct 53 ms 22352 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 4 ms 7772 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 5 ms 9308 KB Output is correct
6 Correct 6 ms 9304 KB Output is correct
7 Correct 5 ms 9320 KB Output is correct
8 Correct 5 ms 9052 KB Output is correct
9 Correct 5 ms 9052 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 3 ms 3252 KB Output is correct
12 Correct 2 ms 3416 KB Output is correct
13 Correct 112 ms 37968 KB Output is correct
14 Correct 107 ms 39408 KB Output is correct
15 Correct 102 ms 35408 KB Output is correct
16 Correct 111 ms 36828 KB Output is correct
17 Correct 84 ms 41044 KB Output is correct
18 Correct 78 ms 34388 KB Output is correct
19 Correct 109 ms 42888 KB Output is correct
20 Correct 91 ms 37080 KB Output is correct
21 Correct 117 ms 45648 KB Output is correct
22 Correct 129 ms 57956 KB Output is correct
23 Correct 63 ms 24464 KB Output is correct
24 Correct 53 ms 22352 KB Output is correct
25 Correct 125 ms 41596 KB Output is correct
26 Correct 110 ms 39580 KB Output is correct
27 Correct 108 ms 39056 KB Output is correct
28 Correct 102 ms 35916 KB Output is correct
29 Correct 75 ms 35172 KB Output is correct
30 Correct 90 ms 40284 KB Output is correct
31 Correct 100 ms 41552 KB Output is correct
32 Correct 108 ms 42168 KB Output is correct
33 Correct 123 ms 53412 KB Output is correct
34 Correct 139 ms 58248 KB Output is correct
35 Correct 66 ms 27408 KB Output is correct
36 Correct 63 ms 27340 KB Output is correct