oj.uz

Submission #584748

# Submission time Handle Problem Language Result Execution time Memory
584748 2022-06-28T01:28:09 Z perchuts Tropical Garden (IOI11_garden) C++17
49 / 100
 218 ms 164904 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include "garden.h"
#include "gardenlib.h"
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e6+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<int>g[maxn], ciclo[maxn], g2[maxn];

int n, f[maxn], dist[maxn], vis[maxn], res[maxn];

// void answer(int x){cout<<x<<endl;}

void dfs(int u,int d){
    vis[u] = 2;
    dist[u] = d;
    for(auto v:g2[u]){
        if(vis[v]!=2)dfs(v,d+1);
    }
}

void compute(int P, int Q,int G[]){
    for(int i=0;i<=2*n;++i){
        vis[i] = dist[i] = 0;
        ciclo[i].clear();
    }
    int cur = P, tciclo = 0;
    while(vis[cur]==0){
        vis[cur] = 1, cur = f[cur];
    }
    while(vis[cur]==1){
        vis[cur] = 2, cur = f[cur], ++tciclo;
    }
    //achei o ciclo da componente de p
    if(vis[P]==1){
        tciclo = 1e9, vis[f[P]] = 2;
        dfs(P,0);
        vis[f[P]] = 0;
    }else{
        cur = P;
        int d = tciclo;
        do{
            dfs(cur, d%tciclo), cur = f[cur], d--;
        } while(cur!=P);
        if(P<n)ciclo[0].pb(tciclo);
    }
    for(int i=0;i<n;++i){
        if(vis[i]&&dist[i]){
            ciclo[dist[i]%tciclo].pb(dist[i]);                
        }
    }
    for(int i=0;i<min(tciclo,3*n);++i){
        sort(all(ciclo[i]));
    }
    for(int i=0;i<Q;++i){
        int cur = G[i], ans = upper_bound(all(ciclo[cur%tciclo]),cur) - begin(ciclo[cur%tciclo]);
        res[i] += ans;
    }
    
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    for(int i=0;i<M;++i){
        int u = R[i][0], v = R[i][1];
        g[u].pb(v), g[v].pb(u);
    }
    //grafo funcional, achar distancia de cada vertice pra p   
    for(int i=0;i<2*n;++i){
        int act = i%n;
        if(i<n||sz(g[act])==1){
            int best = g[act][0];
            if(g[best][0]==act)f[i] = best+n;
            else f[i] = best;
        }else{
            if(g[g[act][1]][0]==act)f[i] = g[act][1] + n;
            else f[i] = g[act][1];
        }
        g2[i].pb(f[i]), g2[f[i]].pb(i);
        // cout<<i<<" "<<f[i]<<endl;
    }

    compute(P,Q,G), compute(P+n,Q,G);

    for(int i=0;i<Q;++i){
        answer(res[i]);
    }
}

// int v[maxn][2], queries[maxn];

// int main(){
//     int n,m,p,q;cin>>n>>m>>p>>q;
//     for(int i=0;i<m;++i){
//         cin>>v[i][0]>>v[i][1];
//     }
//     for(int i=0;i<q;++i)cin>>queries[i];
//     count_routes(n,m,p,v,q,queries);
// }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70868 KB Output is correct
2 Correct 33 ms 70868 KB Output is correct
3 Correct 34 ms 70952 KB Output is correct
4 Correct 33 ms 70808 KB Output is correct
5 Correct 34 ms 70752 KB Output is correct
6 Correct 38 ms 70988 KB Output is correct
7 Correct 34 ms 70740 KB Output is correct
8 Correct 37 ms 70868 KB Output is correct
9 Correct 38 ms 71100 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70868 KB Output is correct
2 Correct 33 ms 70868 KB Output is correct
3 Correct 34 ms 70952 KB Output is correct
4 Correct 33 ms 70808 KB Output is correct
5 Correct 34 ms 70752 KB Output is correct
6 Correct 38 ms 70988 KB Output is correct
7 Correct 34 ms 70740 KB Output is correct
8 Correct 37 ms 70868 KB Output is correct
9 Correct 38 ms 71100 KB Output is correct
10 Correct 36 ms 70736 KB Output is correct
11 Correct 44 ms 73568 KB Output is correct
12 Correct 60 ms 75724 KB Output is correct
13 Correct 80 ms 84128 KB Output is correct
14 Correct 179 ms 88444 KB Output is correct
15 Correct 218 ms 89280 KB Output is correct
16 Correct 136 ms 83608 KB Output is correct
17 Runtime error 166 ms 164904 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70868 KB Output is correct
2 Correct 33 ms 70868 KB Output is correct
3 Correct 34 ms 70952 KB Output is correct
4 Correct 33 ms 70808 KB Output is correct
5 Correct 34 ms 70752 KB Output is correct
6 Correct 38 ms 70988 KB Output is correct
7 Correct 34 ms 70740 KB Output is correct
8 Correct 37 ms 70868 KB Output is correct
9 Correct 38 ms 71100 KB Output is correct
10 Correct 36 ms 70736 KB Output is correct
11 Correct 44 ms 73568 KB Output is correct
12 Correct 60 ms 75724 KB Output is correct
13 Correct 80 ms 84128 KB Output is correct
14 Correct 179 ms 88444 KB Output is correct
15 Correct 218 ms 89280 KB Output is correct
16 Correct 136 ms 83608 KB Output is correct
17 Runtime error 166 ms 164904 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -