oj.uz

Submission #1042266

# Submission time Handle Problem Language Result Execution time Memory
1042266 2024-08-02T18:39:43 Z Lemser Tropical Garden (IOI11_garden) C++14
49 / 100
 5000 ms 16660 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
 
#define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
 
bool cmin(int &a, int b){if(b<a){a=b;return 1;}return 0;}
bool cmax(int &a, int b){if(b>a){a=b;return 1;}return 0;}
void valid(ll in){cout<<((in)?"SI\n":"NO\n");}
ll lcm(ll a, ll b){return (a/gcd(a,b))*b;}
ll gauss(ll n){return (n*(n+1))/2;}
const int N=1e5+5e4+7,INF=1e9;
struct state{
    int u,t;
    state(){}
    state(int u,int t):u(u),t(t){}
};
int mn[N],mn2[N];
state nxt(int u,int t){
    int v=((t^1)?mn[u]:(mn2[u]==-1?mn[u]:mn2[u]));
    int tv=(mn[v]==u?1:0);
    return {v,tv};
}
state nxt(state e){
    int u=e.u,t=e.t;
    int v=((t^1)?mn[u]:(mn2[u]==-1?mn[u]:mn2[u]));
    int tv=(mn[v]==u?1:0);
    return {v,tv};
}
vii graph1[N];
vector<state> graphinv[N][2];
int md1[N][2],md2[N][2];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    fo(i,M){
        graph1[R[i][0]].pb({R[i][1], i});
        graph1[R[i][1]].pb({R[i][0], i});
    }
    fo(i,N){
        mn[i]=mn2[i]=-1;
        int m1=M+1,m2=M+1;
        for(auto [v,w]:graph1[i]){
            if(m1>w)m2=m1,m1=w,mn2[i]=mn[i],mn[i]=v;
            else if(m2>w)m2=w,mn2[i]=v;
        }
    }
    fo(i,N){
        fo(j,2){
            state nx=nxt(i,j);
            graphinv[nx.u][nx.t].pb(state(i,j));
        }
    }
    queue<state>q;
    q.push(state(P, 0));
    md1[P][0]=0;
    while(sz(q)){
        state u=q.front();q.pop();
        for(state v:graphinv[u.u][u.t]){
            if(md1[v.u][v.t]==0){
                md1[v.u][v.t]=md1[u.u][u.t]+1;
                q.push(v);
            }
        }
    }
    q.push(state(P, 1));
    md2[P][1]=0;
    while(sz(q)){
        state u=q.front();q.pop();
        for(state v:graphinv[u.u][u.t]){
            if(md2[v.u][v.t]==0){
                md2[v.u][v.t]=md2[u.u][u.t]+1;
                q.push(v);
            }
        }
    }
    fo(qi,Q){
        int k=G[qi];
        int ans=0;
        fo(i,N){
            int d=k;
            state act=state(i,0);
            while(d--){
                act=nxt(act);
            }
            if(act.u==P)ans++;
        }
        answer(ans);
    }
}

Compilation message

garden.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
garden.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:71:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |         for(auto [v,w]:graph1[i]){
      |                  ^

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14780 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14780 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 14684 KB Output is correct
11 Execution timed out 5091 ms 16660 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 3 ms 14780 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 4 ms 14684 KB Output is correct
11 Execution timed out 5091 ms 16660 KB Time limit exceeded
12 Halted 0 ms 0 KB -