Submission #746565

#	Time	Username	Problem	Language	Result	Execution time	Memory
746565		LucaGreg	Pictionary (COCI18_pictionary)	C++17	140 / 140	62 ms	4488 KiB

pictionary

#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 (stderr)

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

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14