oj.uz

답안 #314672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314672 2020-10-20T18:12:44 Z fivefourthreeone Uzastopni (COCI15_uzastopni) C++17
160 / 160
 68 ms 17916 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = atan(1);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 10001;
const int mxV = 103;
vector<int> adj[mxN];
int arr[mxN];
bitset<mxV> dp[mxN][mxV]; // dp[i][l][r] = possible
bitset<mxV> lft[mxN];
int n;
void solve(int u, int p = -1) {
    vector<int> c;
    for(int v: adj[u]) {
        if(v^p) {
            solve(v, u);
            c.senpai(v);
        }
    }
    sort(c.begin(), c.end(), [&](int a, int b) {
        return arr[a] < arr[b];
    });
    owo(i, 0, c.size()) {
        owo(r, 0, mxV) {
            owo(l, 1, r+1){
                if(dp[c[i]][r][l]) {
                    lft[r]|= lft[l-1];
                }
            }
            lft[r]|=dp[c[i]][r];
        }
    }
    dp[u][arr[u]][arr[u]] = 1;
    dp[u][arr[u]]|=lft[arr[u]-1];
    owo(r, arr[u]+1, mxV) {
        if(lft[r][arr[u]+1]) {
            dp[u][r]|=lft[arr[u]-1];
            dp[u][r][arr[u]] = 1;
        }
    }
    owo(i, 0, mxV) {
        lft[i].reset();
    }
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    owo(i, 0, n) {
        cin>>arr[i];
    }
    int a, b;
    owo(i, 0, n-1) {
        cin>>a>>b;
        a--; b--;
        adj[a].senpai(b);
        adj[b].senpai(a);
    }
    solve(0);
    int ans = 0;
    owo(r, 0, mxV){
        ans+=dp[0][r].count();
    }
    cout<<ans<<"\n";
    return 0;
}

Compilation message

uzastopni.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
uzastopni.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
uzastopni.cpp: In function 'void solve(int, int)':
uzastopni.cpp:5:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define owo(i,a, b) for(auto i=(a);i<(b); ++i)
      |                                     ^
uzastopni.cpp:46:5: note: in expansion of macro 'owo'
   46 |     owo(i, 0, c.size()) {
      |     ^~~

Subtask #1
160.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 65 ms 17016 KB Output is correct
12 Correct 65 ms 17016 KB Output is correct
13 Correct 65 ms 17084 KB Output is correct
14 Correct 68 ms 17916 KB Output is correct
15 Correct 68 ms 17912 KB Output is correct
16 Correct 68 ms 17912 KB Output is correct
17 Correct 65 ms 17016 KB Output is correct
18 Correct 65 ms 17144 KB Output is correct
19 Correct 59 ms 17144 KB Output is correct
20 Correct 62 ms 17144 KB Output is correct