oj.uz

Submission #87181

# Submission time Handle Problem Language Result Execution time Memory
87181 2018-11-29T22:39:39 Z zoooma13 Pictionary (COCI18_pictionary) C++14
140 / 140
 370 ms 14256 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 100005
#define LOG_N 20

int N ,M ,Q;
int A ,B;

int Parent[MAX_N];
int Find(int U){
    return Parent[U] = (Parent[U] == U ? U : Find(Parent[U]));
}
bool Union(int U ,int V){
    U = Find(U) ,V = Find(V);
    if(U != V){
        Parent[U] = V;
        return 1;
    }
    return 0;
}

#define Edge pair<int ,int>
#define to first
#define we second
vector < Edge > Adj[MAX_N];
int depth[MAX_N] ,par[MAX_N] ,ed[MAX_N];
void DFS(int V){
    for(auto&i : Adj[V]) if(i.to != par[V]){
        depth[i.to]  = depth[V]+1;
        par[i.to] = V;
        ed[i.to] = i.we;
        DFS(i.to);
    }
}

int main()
{
    cin >> N >> M >> Q;

    iota(Parent ,Parent+N+1 ,0);
    for(int i=M; i; i--)
    {
        for(int j=i+i; j<=N; j+=i)
            if(Union(i ,j))
                Adj[i].push_back({j ,M-i+1}),
                Adj[j].push_back({i ,M-i+1});
    }

    DFS(1);

    for(int i=0; i<Q; i++)
    {
        cin >> A >> B;

        int ans = 0;
        if(depth[A] < depth[B])
            swap(A ,B);
        for( ; depth[A] > depth[B]; A = par[A])
            ans = max(ans ,ed[A]);
        for( ; A != B; A = par[A] ,B = par[B])
            ans = max(ans ,max(ed[A] ,ed[B]));
        cout << ans << endl;
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2808 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3108 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 3840 KB Output is correct
2 Correct 182 ms 4524 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 5656 KB Output is correct
2 Correct 209 ms 6436 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 7872 KB Output is correct
2 Correct 134 ms 8348 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 9436 KB Output is correct
2 Correct 159 ms 10368 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 11000 KB Output is correct
2 Correct 199 ms 11080 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 12216 KB Output is correct
2 Correct 297 ms 12388 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 12932 KB Output is correct
2 Correct 300 ms 13668 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 14096 KB Output is correct
2 Correct 350 ms 14256 KB Output is correct