oj.uz

Submission #1042287

# Submission time Handle Problem Language Result Execution time Memory
1042287 2024-08-02T19:20:03 Z Lemser Tropical Garden (IOI11_garden) C++14
100 / 100
 979 ms 30956 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)+3;
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], vis[N][2],timer=0;
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    fo(i,N)graph1[i].clear(),graphinv[i][0].clear(),graphinv[i][1].clear();
    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));
            md1[i][j]=md2[i][j]=INF;
        }
    }
    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]==INF){
                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]==INF){
                md2[v.u][v.t]=md2[u.u][u.t]+1;
                q.push(v);
            }
        }
    }
    timer++;
    int toP0=0,toP1=0;
    state act={P,0}; 
    toP0++;
    act=nxt(act);
    while(act.u!=P||act.t!=0){
        vis[act.u][act.t]=timer;
        toP0++;
        act=nxt(act);
        if(vis[act.u][act.t]==timer){
            toP0=INF;
            break;
        }
    }
    act={P,1};
    toP1++;
    act=nxt(act);
    timer++;
    while(act.u!=P||act.t!=1){
        vis[act.u][act.t]=timer;
        toP1++;
        act=nxt(act);
        if(vis[act.u][act.t]==timer){
            toP1=INF;
            break;
        }
    }
    // cout<<toP0<<" "<<toP1<<endl;
    fo(qi,Q){
        int k=G[qi];
        int ans=0;
        fo(i,N){
            if(md1[i][0]<=k&&((k-md1[i][0])%toP0)==0){
                ans++;
                continue;
            }
            if(md2[i][0]<=k&&((k-md2[i][0])%toP1)==0){
                ans++;
                continue;
            }
        }
        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:72:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |         for(auto [v,w]:graph1[i]){
      |                  ^

Subtask #1
49.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14904 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 2 ms 14680 KB Output is correct
11 Correct 7 ms 16728 KB Output is correct
12 Correct 13 ms 16732 KB Output is correct
13 Correct 22 ms 23928 KB Output is correct
14 Correct 41 ms 25884 KB Output is correct
15 Correct 50 ms 26572 KB Output is correct
16 Correct 37 ms 22700 KB Output is correct
17 Correct 37 ms 22580 KB Output is correct
18 Correct 16 ms 16732 KB Output is correct
19 Correct 46 ms 26188 KB Output is correct
20 Correct 57 ms 26196 KB Output is correct
21 Correct 36 ms 23496 KB Output is correct
22 Correct 35 ms 22732 KB Output is correct
23 Correct 43 ms 26964 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14904 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 2 ms 14680 KB Output is correct
11 Correct 7 ms 16728 KB Output is correct
12 Correct 13 ms 16732 KB Output is correct
13 Correct 22 ms 23928 KB Output is correct
14 Correct 41 ms 25884 KB Output is correct
15 Correct 50 ms 26572 KB Output is correct
16 Correct 37 ms 22700 KB Output is correct
17 Correct 37 ms 22580 KB Output is correct
18 Correct 16 ms 16732 KB Output is correct
19 Correct 46 ms 26188 KB Output is correct
20 Correct 57 ms 26196 KB Output is correct
21 Correct 36 ms 23496 KB Output is correct
22 Correct 35 ms 22732 KB Output is correct
23 Correct 43 ms 26964 KB Output is correct
24 Correct 2 ms 12636 KB Output is correct
25 Correct 54 ms 16836 KB Output is correct
26 Correct 85 ms 16728 KB Output is correct
27 Correct 584 ms 23888 KB Output is correct
28 Correct 623 ms 25964 KB Output is correct
29 Correct 653 ms 26196 KB Output is correct
30 Correct 377 ms 22864 KB Output is correct
31 Correct 305 ms 22736 KB Output is correct
32 Correct 93 ms 16728 KB Output is correct
33 Correct 601 ms 25940 KB Output is correct
34 Correct 650 ms 26344 KB Output is correct
35 Correct 369 ms 23556 KB Output is correct
36 Correct 520 ms 22040 KB Output is correct
37 Correct 469 ms 26960 KB Output is correct
38 Correct 979 ms 30956 KB Output is correct