oj.uz

Submission #777360

# Submission time Handle Problem Language Result Execution time Memory
777360 2023-07-09T06:59:00 Z dxz05 Vinjete (COI22_vinjete) C++17
11 / 100
 309 ms 524288 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e5 + 2;

bitset<N> b[N];
vector<tuple<int, int, int>> g[N];

bitset<N> full;

int ans[N];
void dfs(int v, int p){
    ans[v] = (int) b[v].count();

    for (auto [u, l, r] : g[v]){
        if (u == p) continue;
        int k = r - l + 1;

        b[u] = b[v] | ((full >> l) << (N - k) >> (N - k - l));
        dfs(u, v);
    }
}

void solve(){
    int n, m;
    cin >> n >> m;

    for (int i = 1; i < n; i++){
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        g[u].emplace_back(v, l, r);
        g[v].emplace_back(u, l, r);
    }

    full.set();

    dfs(1, -1);

    for (int i = 2; i <= n; i++) cout << ans[i] << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:59:13: warning: unused variable 'startTime' [-Wunused-variable]
   59 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63948 KB Output is correct
2 Correct 26 ms 64024 KB Output is correct
3 Correct 26 ms 63980 KB Output is correct
4 Correct 26 ms 64028 KB Output is correct
5 Correct 26 ms 64016 KB Output is correct
6 Correct 30 ms 63948 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8708 KB Output is correct
9 Correct 13 ms 21524 KB Output is correct
10 Correct 15 ms 20756 KB Output is correct
11 Correct 13 ms 19952 KB Output is correct
12 Correct 14 ms 21288 KB Output is correct
13 Correct 16 ms 22140 KB Output is correct
14 Correct 14 ms 21076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 11 ms 15700 KB Output is correct
18 Correct 12 ms 16016 KB Output is correct
19 Correct 11 ms 15812 KB Output is correct
20 Correct 11 ms 16144 KB Output is correct
21 Correct 13 ms 15888 KB Output is correct
22 Correct 11 ms 15888 KB Output is correct
23 Correct 3 ms 4692 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63948 KB Output is correct
2 Correct 26 ms 64024 KB Output is correct
3 Correct 26 ms 63980 KB Output is correct
4 Correct 26 ms 64028 KB Output is correct
5 Correct 26 ms 64016 KB Output is correct
6 Correct 30 ms 63948 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8708 KB Output is correct
9 Correct 13 ms 21524 KB Output is correct
10 Correct 15 ms 20756 KB Output is correct
11 Correct 13 ms 19952 KB Output is correct
12 Correct 14 ms 21288 KB Output is correct
13 Correct 16 ms 22140 KB Output is correct
14 Correct 14 ms 21076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 11 ms 15700 KB Output is correct
18 Correct 12 ms 16016 KB Output is correct
19 Correct 11 ms 15812 KB Output is correct
20 Correct 11 ms 16144 KB Output is correct
21 Correct 13 ms 15888 KB Output is correct
22 Correct 11 ms 15888 KB Output is correct
23 Correct 3 ms 4692 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct
25 Incorrect 26 ms 63956 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63948 KB Output is correct
2 Correct 26 ms 64024 KB Output is correct
3 Correct 26 ms 63980 KB Output is correct
4 Correct 26 ms 64028 KB Output is correct
5 Correct 26 ms 64016 KB Output is correct
6 Correct 30 ms 63948 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8708 KB Output is correct
9 Correct 13 ms 21524 KB Output is correct
10 Correct 15 ms 20756 KB Output is correct
11 Correct 13 ms 19952 KB Output is correct
12 Correct 14 ms 21288 KB Output is correct
13 Correct 16 ms 22140 KB Output is correct
14 Correct 14 ms 21076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 11 ms 15700 KB Output is correct
18 Correct 12 ms 16016 KB Output is correct
19 Correct 11 ms 15812 KB Output is correct
20 Correct 11 ms 16144 KB Output is correct
21 Correct 13 ms 15888 KB Output is correct
22 Correct 11 ms 15888 KB Output is correct
23 Correct 3 ms 4692 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct
25 Runtime error 309 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63948 KB Output is correct
2 Correct 26 ms 64024 KB Output is correct
3 Correct 26 ms 63980 KB Output is correct
4 Correct 26 ms 64028 KB Output is correct
5 Correct 26 ms 64016 KB Output is correct
6 Correct 30 ms 63948 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8708 KB Output is correct
9 Correct 13 ms 21524 KB Output is correct
10 Correct 15 ms 20756 KB Output is correct
11 Correct 13 ms 19952 KB Output is correct
12 Correct 14 ms 21288 KB Output is correct
13 Correct 16 ms 22140 KB Output is correct
14 Correct 14 ms 21076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 11 ms 15700 KB Output is correct
18 Correct 12 ms 16016 KB Output is correct
19 Correct 11 ms 15812 KB Output is correct
20 Correct 11 ms 16144 KB Output is correct
21 Correct 13 ms 15888 KB Output is correct
22 Correct 11 ms 15888 KB Output is correct
23 Correct 3 ms 4692 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct
25 Runtime error 309 ms 524288 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 63948 KB Output is correct
2 Correct 26 ms 64024 KB Output is correct
3 Correct 26 ms 63980 KB Output is correct
4 Correct 26 ms 64028 KB Output is correct
5 Correct 26 ms 64016 KB Output is correct
6 Correct 30 ms 63948 KB Output is correct
7 Correct 4 ms 8788 KB Output is correct
8 Correct 4 ms 8708 KB Output is correct
9 Correct 13 ms 21524 KB Output is correct
10 Correct 15 ms 20756 KB Output is correct
11 Correct 13 ms 19952 KB Output is correct
12 Correct 14 ms 21288 KB Output is correct
13 Correct 16 ms 22140 KB Output is correct
14 Correct 14 ms 21076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 11 ms 15700 KB Output is correct
18 Correct 12 ms 16016 KB Output is correct
19 Correct 11 ms 15812 KB Output is correct
20 Correct 11 ms 16144 KB Output is correct
21 Correct 13 ms 15888 KB Output is correct
22 Correct 11 ms 15888 KB Output is correct
23 Correct 3 ms 4692 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct
25 Incorrect 26 ms 63956 KB Output isn't correct
26 Halted 0 ms 0 KB -