oj.uz

답안 #1076430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1076430 2024-08-26T13:48:34 Z clementine Pictionary (COCI18_pictionary) C++17
0 / 140
 90 ms 26308 KB 
#include<bits/stdc++.h>
using namespace std;

int par[100005];
int sz[100005];
// tree after dsu first int is edge, second is weight
vector<pair<int ,int>> graph[100005];
int maxs[100005][20];
int parent[100005][20];
bool visited[100005];
int h[100005];

void construct(int n)
{
    for(int i = 0; i <=n; i ++)
    {
        par[i] = i;
        sz[i] = 1;
    }
}
int find(int a)
{
    if(par[a] !=a)
    {
        par[a] = find(par[a]);
        return par[a];
    }
    return a;
}
void unite(int x, int y, int w)
{
    int a = find(x);
    int b = find(y);
    if(a!=b)
    {
        if(sz[a] > sz[b])
        {
            swap(a, b);
        }
        par[a] = b;
        sz[b] +=sz[a];
        graph[b].push_back({a, w});
        graph[a].push_back({b, w});
    }
}

void dfs(int u )
{
    visited[u] = true;
    for(auto v:graph[u])
    {
        if(!visited[v.first])
        {
            parent[v.first][0] = u;
            maxs[v.first][0] = v.second;
            h[v.first] = h[u] - 1;
            dfs(v.first);
        }
    }
}
int findmin(int x, int y)
{
    int ans = 0;
    if(h[x] < h[y])
    {
        swap(x, y);
    }
    int d = h[x] - h[y];
    for(int i = 0; i <20; i ++)
    {
        if((1<<i) && d)
        {
            ans = max(ans, maxs[x][i]);
            x = parent[x][i];
        }
    }
    for(int i = 19; i >=1; i --)
    {
        if(parent[x][i] != parent[y][i])
        {
            ans = max(ans, maxs[x][i]);
            ans = max(ans, maxs[y][i]);
            x = parent[x][i];
            y = parent[y][i];
        }
    }
    ans = max(ans, maxs[x][0]);
    ans= max(ans, maxs[y][0]);
    return ans;
}





int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> queries;
    for(int i = 0, a, b; i <q; i ++)
    {
        cin >> a >> b;
        queries.push_back({a, b});
    }
    construct(n);
    for(int i = m; i >=1; i --)
    {
        for(int f = 2; f* i <=n; f ++)
        {
            int a =find(i);
            int b = find(f * i);
            if (a!= b)
            {
                unite(a, b,  m - i + 1);
            }
        }
    }
    /*
    for(int i = 1; i <=n; i ++)
    {
        for(auto v: graph[i])
        {
            cout<< i << " " << v.first << " " << v.second << '\n';
        }
    }*/
    int root = find(1);
    maxs[root][0] = 0;
    dfs(root);
    for(int k = 1; (1 << k) <=n; k ++)
    {   
        for(int i = 1; i <=n; i ++)
        {
            maxs[i][k] = max(maxs[i][k-1], maxs[parent[i][k-1]][k-1]);
            parent[i][k] = parent[parent[i][k-1]][k-1];
        }

    }
    for(auto q:queries)
    {
        cout << findmin(q.first, q.second) << '\n';
    }

}

Compilation message

pictionary.cpp: In function 'int findmin(int, int)':
pictionary.cpp:71:14: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   71 |         if((1<<i) && d)
      |            ~~^~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 3288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 4300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 8404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 10440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 14020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 17608 KB Output is correct
2 Incorrect 63 ms 19420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 71 ms 21192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 26308 KB Output isn't correct
2 Halted 0 ms 0 KB -