oj.uz

Submission #909005

# Submission time Handle Problem Language Result Execution time Memory
909005 2024-01-17T04:28:05 Z bachhoangxuan 물병 (JOI14_bottle) C++17
100 / 100
 1199 ms 124184 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int mod=998244353;
const int maxn=2005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=200005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
const int base=131;

int dx[]={0,0,1,-1},
    dy[]={1,-1,0,0};

int n,m,p,q,res[maxq];
char c[maxn][maxn];
int f[maxn][maxn],d[maxn][maxn];

vector<piii> s[maxq];
int par[maxq];

int findpar(int u){
    if(u!=par[u]) return par[u]=findpar(par[u]);
    return u;
}
void unions(int u,int v,int w){
    u=findpar(u);v=findpar(v);
    if(u==v) return;
    if((int)s[u].size()<(int)s[v].size()) swap(u,v);
    for(auto [id,x]:s[v]){
        x.fi=findpar(x.fi);
        x.se=findpar(x.se);
        if(x.fi==x.se) continue;
        if(min(x.fi,x.se)==min(u,v) && max(x.fi,x.se)==max(u,v)) res[id]=w;
        else s[u].push_back({id,x});
    }
    par[v]=u;
}

void solve(){
    cin >> n >> m >> p >> q;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> c[i][j];
    queue<pii> qq;
    for(int i=1;i<=p;i++){
        par[i]=i;
        int x,y;cin >> x >> y;
        f[x][y]=i;qq.push({x,y});
    }
    while(!qq.empty()){
        int x=qq.front().fi,y=qq.front().se;qq.pop();
        for(int t=0;t<4;t++){
            int xt=x+dx[t],yt=y+dy[t];
            if(xt<=0 || yt<=0 || xt>n || yt>m || f[xt][yt] || c[xt][yt]=='#') continue;
            d[xt][yt]=d[x][y]+1;
            f[xt][yt]=f[x][y];
            qq.push({xt,yt});
        }
    }
    vector<piii> e;
    for(int x=1;x<=n;x++) for(int y=1;y<=m;y++){
        if(!f[x][y]) continue;
        for(int t=0;t<4;t++){
            int xt=x+dx[t],yt=y+dy[t];
            if(xt<=0 || yt<=0 || xt>n || yt>m || !f[xt][yt] || f[xt][yt]==f[x][y]) continue;
            e.push_back({d[xt][yt]+d[x][y],{f[xt][yt],f[x][y]}});
        }
    }
    for(int i=1;i<=q;i++){
        int u,v;cin >> u >> v;res[i]=-1;
        s[u].push_back({i,{u,v}});
        s[v].push_back({i,{u,v}});
    }
    sort(e.begin(),e.end());
    for(auto x:e) unions(x.se.fi,x.se.se,x.fi);
    for(int i=1;i<=q;i++) cout << res[i] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 6 ms 17496 KB Output is correct
3 Correct 8 ms 17500 KB Output is correct
4 Correct 55 ms 35576 KB Output is correct
5 Correct 64 ms 35100 KB Output is correct
6 Correct 57 ms 37048 KB Output is correct
7 Correct 53 ms 34592 KB Output is correct
8 Correct 57 ms 38328 KB Output is correct
9 Correct 56 ms 37804 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35632 KB Output is correct
2 Correct 34 ms 18524 KB Output is correct
3 Correct 405 ms 46600 KB Output is correct
4 Correct 499 ms 50480 KB Output is correct
5 Correct 536 ms 54468 KB Output is correct
6 Correct 427 ms 46460 KB Output is correct
7 Correct 566 ms 49260 KB Output is correct
8 Correct 620 ms 53404 KB Output is correct
9 Correct 572 ms 60044 KB Output is correct
10 Correct 348 ms 47136 KB Output is correct
11 Correct 495 ms 48904 KB Output is correct
12 Correct 166 ms 45168 KB Output is correct
13 Correct 163 ms 43040 KB Output is correct
14 Correct 126 ms 47096 KB Output is correct
15 Correct 174 ms 43088 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35624 KB Output is correct
2 Correct 34 ms 17996 KB Output is correct
3 Correct 220 ms 42580 KB Output is correct
4 Correct 567 ms 46464 KB Output is correct
5 Correct 631 ms 52812 KB Output is correct
6 Correct 539 ms 61040 KB Output is correct
7 Correct 302 ms 47704 KB Output is correct
8 Correct 461 ms 49328 KB Output is correct
9 Correct 173 ms 46108 KB Output is correct
10 Correct 142 ms 44472 KB Output is correct
11 Correct 145 ms 42664 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 69180 KB Output is correct
2 Correct 794 ms 93996 KB Output is correct
3 Correct 296 ms 47292 KB Output is correct
4 Correct 999 ms 102792 KB Output is correct
5 Correct 1199 ms 115564 KB Output is correct
6 Correct 645 ms 86240 KB Output is correct
7 Correct 334 ms 47060 KB Output is correct
8 Correct 107 ms 42744 KB Output is correct
9 Correct 923 ms 124184 KB Output is correct
10 Correct 748 ms 103340 KB Output is correct
11 Correct 924 ms 121688 KB Output is correct
12 Correct 775 ms 112388 KB Output is correct