oj.uz

Submission #746565

# Submission time Handle Problem Language Result Execution time Memory
746565 2023-05-22T19:30:38 Z LucaGreg Pictionary (COCI18_pictionary) C++17
140 / 140
 62 ms 4488 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ff first
#define ss second
#define int long long int
 
const int INF = 2000000000000000;
const int mod = 1000000007;
 
int sz[100010];
pair<int, int> pai[100010];
 
int find(int v){
    if(pai[v].ff==v) return v;
    return find(pai[v].ff);
}
 
void join(int a, int b, int w){ 
    a = find(a);
    b = find(b);
    if(a==b) return;
    if(sz[a]>sz[b]) swap(a, b);
    sz[b] += sz[a];
    pai[a].ff = b;
    pai[a].ss = w;
}
 
int query(int a, int b){
    int repA = find(a);
    int repB = find(b);
    if(repA!=repB) return -1;
    if(a==b) return 0;
    set<pair<int, int> > listaA;
    int aCurW = 0;
    while(pai[a].ff!=a){
        listaA.insert({a, aCurW});
        aCurW = max(aCurW, pai[a].ss);
        a = pai[a].ff;
    }
    listaA.insert({a, aCurW});
    int bCurW = 0;
    while(pai[b].ff!=b){
        auto it = listaA.lower_bound({b, -INF});
        if(it!=listaA.end() && (*it).ff==b) return max(bCurW, (*it).ss);
        bCurW = max(bCurW, pai[b].ss);
        b = pai[b].ff;
    }
    return max(aCurW, bCurW);
}
 
 
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(0);
    int n, m, q; cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        sz[i] = 1;
        pai[i].ff = i;
        pai[i].ss = 0;
    }
    int curMdc = m;
    for(int i=1;i<=m;i++){
        for(int j=2;(j*curMdc)<=n;j++){
            join(curMdc, j*curMdc, i);
        }
        curMdc--;
    }
    for(int i=1;i<=q;i++){
        int a, b; cin>>a>>b;
        cout<<query(a, b)<<"\n";
    }
 
 
 
    return 0;
}

Compilation message

pictionary.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main()
      | ^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 560 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1084 KB Output is correct
2 Correct 21 ms 1196 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1572 KB Output is correct
2 Correct 30 ms 1356 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1584 KB Output is correct
2 Correct 23 ms 1492 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1880 KB Output is correct
2 Correct 23 ms 1876 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2524 KB Output is correct
2 Correct 30 ms 2264 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3112 KB Output is correct
2 Correct 46 ms 3404 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3732 KB Output is correct
2 Correct 55 ms 3916 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4488 KB Output is correct
2 Correct 58 ms 4392 KB Output is correct