oj.uz

Submission #1022320

# Submission time Handle Problem Language Result Execution time Memory
1022320 2024-07-13T12:02:51 Z yeediot File Paths (BOI15_fil) C++17
100 / 100
 82 ms 24580 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void CHECK();
void setio(){
    freopen("/Users/iantsai/cpp/input.txt","r",stdin);
    freopen("/Users/iantsai/cpp/output.txt","w",stdout);
}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
#define TOI_is_so_de ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);setio();
const int mxn = 6005, mxC = 1e7 + 5, shift = 1e7;
vector<int>adj[mxn];
int n, m, k, l, d[mxn], ans[mxn], f[2][2 * mxC], in[mxn], out[mxn], tmr;
void dfs(int v){
    in[v] = ++tmr;
    for(auto u : adj[v]){
        d[u] += d[v];
        dfs(u);
    }
    out[v] = tmr;
}
void calc(int v){
    if(v > n){
        if(f[1][k - d[v] + shift]) ans[v] = 1;
        else{
            for(int i = 1; i * i <= k - d[v]; i++){
                if((k - d[v]) % i) continue;
                if(f[0][i] or f[0][(k - d[v]) / i]){
                    ans[v] = 1;
                    return;
                }
            }
        }
        return;
    }
    for(int i = 0; i <= n; i++){
        if(in[v] <= in[i] and out[i] <= out[v]){
            f[0][d[i] - d[v] + l + 1]++;
        }
        else{
            f[1][d[i] + l + 1 - d[v] + shift]++;
        }
    }
    for(auto u : adj[v]){
        calc(u);
    }
    for(int i = 0; i <= n; i++){
        if(in[v] <= in[i] and out[i] <= out[v]){
            f[0][d[i] - d[v] + l + 1]--;
        }
        else{
            f[1][d[i] + l + 1 - d[v] + shift]--;
        }
    }
}
void solve(){
    cin >> n >> m >> k >> l;
    for(int i = 1, p; i <= n + m; i++){
        cin >> p >> d[i];
        adj[p].pb(i);
        d[i]++; 
    }
    dfs(0);
    f[1][shift] = 1;
    calc(0);
    for(int i = n + 1; i <= n + m; i++){
        cout << (ans[i] ? "YES\n" : "NO\n");
    }
}
signed main(){
    TOI_is_so_de;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef local
    CHECK();
    #endif
}
/*
input:
 
*/
#ifdef local
void CHECK(){
    cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    function<bool(string,string)> compareFiles = [](string p1, string p2)->bool {
        std::ifstream file1(p1);
        std::ifstream file2(p2);
        if(!file1.is_open() || !file2.is_open()) return false;
        std::string line1, line2;
        while (getline(file1, line1) && getline(file2, line2)) {
            if (line1 != line2)return false;
        }
        int cnta = 0, cntb = 0;
        while(getline(file1,line1))cnta++;
        while(getline(file2,line2))cntb++;
        return cntb - cnta <= 1;
    };
    bool check = compareFiles("output.txt","expected.txt");
    if(check) cerr<<"ACCEPTED\n";
    else cerr<<"WRONG ANSWER!\n";
}
#else
#endif

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 3 ms 2904 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 12 ms 23388 KB Output is correct
6 Correct 10 ms 20060 KB Output is correct
7 Correct 12 ms 23132 KB Output is correct
8 Correct 13 ms 20312 KB Output is correct
9 Correct 14 ms 20316 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 1628 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 23224 KB Output is correct
2 Correct 59 ms 23376 KB Output is correct
3 Correct 62 ms 23244 KB Output is correct
4 Correct 59 ms 23376 KB Output is correct
5 Correct 82 ms 24404 KB Output is correct
6 Correct 66 ms 24564 KB Output is correct
7 Correct 65 ms 24408 KB Output is correct
8 Correct 68 ms 24496 KB Output is correct
9 Correct 59 ms 23896 KB Output is correct
10 Correct 54 ms 23632 KB Output is correct
11 Correct 21 ms 1116 KB Output is correct
12 Correct 29 ms 6184 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 3 ms 2904 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 12 ms 23388 KB Output is correct
6 Correct 10 ms 20060 KB Output is correct
7 Correct 12 ms 23132 KB Output is correct
8 Correct 13 ms 20312 KB Output is correct
9 Correct 14 ms 20316 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 1628 KB Output is correct
13 Correct 55 ms 23224 KB Output is correct
14 Correct 59 ms 23376 KB Output is correct
15 Correct 62 ms 23244 KB Output is correct
16 Correct 59 ms 23376 KB Output is correct
17 Correct 82 ms 24404 KB Output is correct
18 Correct 66 ms 24564 KB Output is correct
19 Correct 65 ms 24408 KB Output is correct
20 Correct 68 ms 24496 KB Output is correct
21 Correct 59 ms 23896 KB Output is correct
22 Correct 54 ms 23632 KB Output is correct
23 Correct 21 ms 1116 KB Output is correct
24 Correct 29 ms 6184 KB Output is correct
25 Correct 77 ms 23212 KB Output is correct
26 Correct 61 ms 23132 KB Output is correct
27 Correct 59 ms 23380 KB Output is correct
28 Correct 57 ms 23464 KB Output is correct
29 Correct 61 ms 24580 KB Output is correct
30 Correct 69 ms 24404 KB Output is correct
31 Correct 71 ms 24412 KB Output is correct
32 Correct 64 ms 24400 KB Output is correct
33 Correct 68 ms 23892 KB Output is correct
34 Correct 54 ms 23888 KB Output is correct
35 Correct 23 ms 860 KB Output is correct
36 Correct 32 ms 3420 KB Output is correct