oj.uz

Submission #963150

# Submission time Handle Problem Language Result Execution time Memory
963150 2024-04-14T15:14:03 Z Amr Tropical Garden (IOI11_garden) C++17
69 / 100
 474 ms 179336 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(),(x).end()
const int N = 1000000;
const int Log = 32;
vector<pair<ll,ll> > v[N];
ll lst[N];
vector<ll> vec;
ll vis[N];
pair<ll,ll> sp[N][Log][2];
void dfs1(ll x)
{
    if(vis[x]) return;
    vis[x] = 1;
    vec.push_back(x);
    for(int i = 0; i < v[x].sz; i++)
    {
        dfs1(v[x][i].S);
    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    for(int i = 0; i < M; i++)
    {
        ll x = R[i][0] , y = R[i][1];
        v[x].push_back({i,y});
        v[y].push_back({i,x});
    }
    for(int i = 0; i < N; i++) sort(all(v[i]));


    dfs1(P);
    if(vec.sz==2)
    {
        answer(1);
        return;
    }
    for(int i = 0; i < vec.sz; i++)
    {
        ll x = vec[i];
        ll y = v[x][0].S;
        ll m = -1;
        if(v[y][0].S==x) m = 0; else if(v[y][1].S==x) m = 1;
        sp[x][0][0] = {y,m};


        if(v[x].sz==1) {sp[x][0][1] = {-1,-1}; continue;}

        m = -1;
        y = v[x][1].S;
        if(v[y][0].S==x) m = 0; else if(v[y][1].S==x) m = 1;
        sp[x][0][1] = {y,m};
    }
    for(int j = 1; j < Log; j++)
    {
        for(int i = 0; i < vec.sz; i++)
        {
            ll x = vec[i];
            ll y = sp[x][j-1][0].F,m=0;
            if(v[y].sz>1&&sp[x][j-1][0].S==0) m = 1;
            sp[x][j][0] = sp[y][j-1][m];
            if(v[x].sz==1) continue;

                 y = sp[x][j-1][1].F,m=0;
                if(v[y].sz>1&&sp[x][j-1][1].S==0) m = 1;
                sp[x][j][1] = sp[y][j-1][m];
        }
    }
    /*for(int i = 0; i < N; i++){

        for(int j = 0; j < 3; j++)
        {
            cout << sp[i][j][0].F <<  " " << sp[i][j][1].F << endl;
        }
        cout << endl;
    }*/


        ll ans = 0;
        for(int i = 0; i < vec.sz; i++)
        {
            ll x = vec[i], y = 0;
            ll k = G[0];
            for(int j = Log-1; j >= 0; j--)
            {
                if(k<(1LL<<j)) continue;
                k-=(1LL<<j);
                ll x2 = sp[x][j][y].F,m = sp[x][j][y].S;
                if(m==0&&v[x2].sz>1) m = 1; else m = 0;
                x = x2, y = m;
            }
            //cout << x << " ";
            if(x==P) ans++;
        }
        answer(ans);


}

Compilation message

garden.cpp: In function 'void dfs1(ll)':
garden.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < vec.sz; i++)
      |                      ^
garden.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i = 0; i < vec.sz; i++)
      |                          ^
garden.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int i = 0; i < vec.sz; i++)
      |                          ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31324 KB Output is correct
2 Correct 7 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 8 ms 31580 KB Output is correct
7 Correct 7 ms 29136 KB Output is correct
8 Correct 7 ms 31576 KB Output is correct
9 Correct 11 ms 31832 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31324 KB Output is correct
2 Correct 7 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 8 ms 31580 KB Output is correct
7 Correct 7 ms 29136 KB Output is correct
8 Correct 7 ms 31576 KB Output is correct
9 Correct 11 ms 31832 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 22 ms 42960 KB Output is correct
12 Correct 120 ms 72924 KB Output is correct
13 Correct 273 ms 124884 KB Output is correct
14 Correct 420 ms 176776 KB Output is correct
15 Correct 474 ms 178444 KB Output is correct
16 Correct 261 ms 133108 KB Output is correct
17 Correct 257 ms 117840 KB Output is correct
18 Correct 111 ms 72916 KB Output is correct
19 Correct 423 ms 176628 KB Output is correct
20 Correct 380 ms 179336 KB Output is correct
21 Correct 267 ms 133796 KB Output is correct
22 Correct 312 ms 117384 KB Output is correct
23 Correct 96 ms 133592 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31324 KB Output is correct
2 Correct 7 ms 31320 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 29020 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 8 ms 31580 KB Output is correct
7 Correct 7 ms 29136 KB Output is correct
8 Correct 7 ms 31576 KB Output is correct
9 Correct 11 ms 31832 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 22 ms 42960 KB Output is correct
12 Correct 120 ms 72924 KB Output is correct
13 Correct 273 ms 124884 KB Output is correct
14 Correct 420 ms 176776 KB Output is correct
15 Correct 474 ms 178444 KB Output is correct
16 Correct 261 ms 133108 KB Output is correct
17 Correct 257 ms 117840 KB Output is correct
18 Correct 111 ms 72916 KB Output is correct
19 Correct 423 ms 176628 KB Output is correct
20 Correct 380 ms 179336 KB Output is correct
21 Correct 267 ms 133796 KB Output is correct
22 Correct 312 ms 117384 KB Output is correct
23 Correct 96 ms 133592 KB Output is correct
24 Incorrect 7 ms 29016 KB Output isn't correct
25 Halted 0 ms 0 KB -