oj.uz

Submission #985830

# Submission time Handle Problem Language Result Execution time Memory
985830 2024-05-19T03:58:28 Z hengliao File Paths (BOI15_fil) C++17
33 / 100
 122 ms 74648 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;
    }
    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 3 ms 3164 KB Output is correct
3 Correct 5 ms 7704 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 7 ms 9308 KB Output is correct
6 Correct 5 ms 9304 KB Output is correct
7 Correct 5 ms 9304 KB Output is correct
8 Correct 7 ms 9048 KB Output is correct
9 Correct 5 ms 9052 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 74648 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 3 ms 3164 KB Output is correct
3 Correct 5 ms 7704 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 7 ms 9308 KB Output is correct
6 Correct 5 ms 9304 KB Output is correct
7 Correct 5 ms 9304 KB Output is correct
8 Correct 7 ms 9048 KB Output is correct
9 Correct 5 ms 9052 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 3 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Runtime error 122 ms 74648 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -