oj.uz

Submission #168168

# Submission time Handle Problem Language Result Execution time Memory
168168 2019-12-11T18:08:45 Z rzbt Pictionary (COCI18_pictionary) C++14
140 / 140
 90 ms 10716 KB 
#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

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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3704 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4344 KB Output is correct
2 Correct 28 ms 4412 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4728 KB Output is correct
2 Correct 36 ms 4712 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5424 KB Output is correct
2 Correct 30 ms 5344 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6008 KB Output is correct
2 Correct 34 ms 6224 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7100 KB Output is correct
2 Correct 41 ms 6904 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7960 KB Output is correct
2 Correct 66 ms 8724 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9168 KB Output is correct
2 Correct 76 ms 9988 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 10716 KB Output is correct
2 Correct 87 ms 10596 KB Output is correct