oj.uz

Submission #1119085

# Submission time Handle Problem Language Result Execution time Memory
1119085 2024-11-26T15:38:31 Z Marco_Escandon Tropical Garden (IOI11_garden) C++11
0 / 100
 1 ms 788 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
#pragma once 
vector<vector<ll>>cad;vector<vector<pair<ll,ll>>>v,cad2;
ll p;
pair<ll,ll> dfs(ll node, ll pl)
{
    if(node==p) return {0,pl};
    if(v[pl][node].first!=1e16) return v[pl][node];
    v[pl][node]={1e17,pl};
    v[pl][node]=dfs(cad[node][pl],min((ll)(cad[cad[node][pl]][0]==node),(ll)cad[cad[node][pl]].size()-1));
    v[pl][node].first++;
    return v[pl][node];
}
pair<ll,ll> dfs2(ll node, ll pl)
{
    if(node==p&&v[pl][node].x==1e17) return {0,0};
    if(v[pl][node].first!=1e16) return v[pl][node];
    v[pl][node]={1e17,pl};
    v[pl][node]=dfs(cad[node][pl],min((ll)(cad[cad[node][pl]][0]==node),(ll)cad[cad[node][pl]].size()-1));
    v[pl][node].first++;
    return v[pl][node];
}
ll dfs3(ll node, ll pl, ll k)
{
    if(node==p&&k==0) return 1;
    if(k<=0) return 0;
    return dfs3(cad[node][pl],min((ll)(cad[cad[node][pl]][0]==node),(ll)cad[cad[node][pl]].size()-1),k-1);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    ll n=N,m=M;
    p=P;
    cad.resize(n+2);
    cad2.resize(n+2);
    v.assign(4,vector<pair<ll,ll>>(n+2,{1e16,0}));
    for(int i=0; i<m; i++)
    {
        ll a=R[i][0],b=R[i][1];
        cad2[a].push_back({i,b});
        cad2[b].push_back({i,a});
    }
    for(int i=0; i<=n; i++)
    {
        sort(cad2[i].begin(),cad2[i].end());
        for(int j=0; j<min((ll)2,(ll)cad2[i].size()); j++)
            cad[i].push_back(cad2[i][j].y);
    }
    for(int i=0; i<n; i++)
    {
        dfs(i,0);
        dfs(i,min((ll)cad[i].size()-1,(ll)1));
    }
    dfs2(p,0);
    dfs2(p,min((ll)cad[p].size()-1,(ll)1));
    ll q=Q;
    for(int z=0; z<q; z++)
    {
        ll a=G[z];
        ll cont=0;
        for(int i=0; i<n; i++)
        {
            if(a>=v[0][i].first||i==p)
            {
                ll b=a-v[0][i].first;
                if(i==p) b=a;
                cont+=((b%v[v[0][i].y][p].x)==0);
            }
        }
        cout<<cont<<" ";
    }
}

Compilation message

garden.cpp:7:9: warning: #pragma once in main file
    7 | #pragma once
      |         ^~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 788 KB Output isn't correct
2 Halted 0 ms 0 KB -