Submission #168168

#	Time	Username	Problem	Language	Result	Execution time	Memory
168168		rzbt	Pictionary (COCI18_pictionary)	C++14	140 / 140	90 ms	10716 KiB

pictionary

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

int n,m,q;
vector<pair<int,int>  > niz[MAXN];

ll res=LLONG_MAX;
int cale[MAXN],masa[MAXN];
int koren(int p){
    while(p!=cale[p])
        p=cale[p];
    return p;
}
void spoji(int a,int b,int grana){
    a=koren(a);
    b=koren(b);
    if(a==b)return;
    if(masa[a]<masa[b])swap(a,b);
    masa[a]+=masa[b];
    cale[b]=a;
    niz[a].pb(mp(b,grana));
    niz[b].pb(mp(a,grana));
}

int dubina[MAXN],otac[MAXN],ograna[MAXN];

void dfs(int t,int o,int grana,int h){
    if(o){
        otac[t]=o;
        ograna[t]=grana;
    }
    dubina[t]=h;
    for(auto x:niz[t]){
        if(x.F==o)continue;
        dfs(x.F,t,x.S,h+1);
    }
}

int dobij(int a,int b){

    int res=1;
    if(dubina[b]>dubina[a])swap(a,b);
    while(dubina[a]>dubina[b]){
        res=max(res,ograna[a]);
        a=otac[a];
    }
    while(a!=b){
        res=max(res,ograna[a]);
        a=otac[a];
        res=max(res,ograna[b]);
        b=otac[b];
    }
    return res;
}

int main()
{
    for(int i=0;i<MAXN;i++){
        cale[i]=i;
        masa[i]=1;
    }
    scanf("%d %d %d", &n, &m, &q);
    for(int i=m;i>=1;i--)
        for(int j=i+i;j<=n;j+=i)
            spoji(j-i,j,m-i+1);

    dfs(koren(1),0,0,0);

    while(q--){
        int t1,t2;
        scanf("%d %d", &t1, &t2),
        printf("%d\n",dobij(t1,t2));

    }


    return 0;
}

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:80:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2),
         ~~~~~~~~~~~~~~~~~~~~~~~~^~
         printf("%d\n",dobij(t1,t2));
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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