oj.uz

Submission #249686

# Submission time Handle Problem Language Result Execution time Memory
249686 2020-07-15T14:34:05 Z Mercenary Pictionary (COCI18_pictionary) C++14
140 / 140
 123 ms 22848 KB 
//how ? boruvska + lca

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int logn = log2(maxn) + 1;

int n , m , q;
vector<ii> adj[maxn];
int vis[maxn];
int lab[maxn];
int FindLab(int u){
    return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}
void Merge(int u , int v , int c){
    u = FindLab(u) , v = FindLab(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u , v);
    lab[u] += lab[v];lab[v] = u;
    adj[u].pb(mp(v,c));
    adj[v].pb(mp(u,c));
}

int M[maxn][logn] , P[maxn][logn];
int dep[maxn];

void dfs(int u , int par){
    for(auto & c : adj[u]){
        if(c.first == par)continue;
        M[c.first][0] = c.second;
        P[c.first][0] = u;
        dep[c.first] = dep[u] + 1;
        for(int i = 1 ; i < logn ; ++i){
            P[c.first][i] = P[P[c.first][i - 1]][i - 1];
            M[c.first][i] = max(M[c.first][i - 1] , M[P[c.first][i - 1]][i - 1]);
        }
        dfs(c.first , u);
    }
}

int getm(int u , int v){
    int res = 0;
    if(dep[u] < dep[v])swap(u , v);
    for(int i = 0 ; i < logn ; ++i){
        if((dep[u] - dep[v]) & (1 << i)){
            res = max(res , M[u][i]);
            u = P[u][i];
        }
    }
    if(u == v)return res;
    for(int i = logn - 1 ; i >= 0 ; --i){
        if(P[u][i] != P[v][i]){
            res = max(res , M[u][i]);
            res = max(res , M[v][i]);
            u = P[u][i];
            v = P[v][i];
        }
    }
    res = max(res , M[u][0]);
    res = max(res , M[v][0]);
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    memset(lab,-1,sizeof lab);
    cin >> n >> m >> q;
    for(int i = m ; i >= 1 ; --i){
        int a = -1 , b = -1;
        for(int j = i * 2 ; j <= n ; j += i){
            Merge(i,j,m+1-i);
        }
    }
    dfs(1,0);
    while(q--){
        int u , v;cin >> u >> v;
        cout << getm(u , v) << '\n';
    }
}

Compilation message

pictionary.cpp: In function 'int main()':
pictionary.cpp:89:13: warning: unused variable 'a' [-Wunused-variable]
         int a = -1 , b = -1;
             ^
pictionary.cpp:89:22: warning: unused variable 'b' [-Wunused-variable]
         int a = -1 , b = -1;
                      ^
pictionary.cpp:83:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:84:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3328 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3456 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4600 KB Output is correct
2 Correct 33 ms 4472 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7800 KB Output is correct
2 Correct 31 ms 7800 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 9720 KB Output is correct
2 Correct 57 ms 10312 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12408 KB Output is correct
2 Correct 61 ms 12664 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 15340 KB Output is correct
2 Correct 99 ms 17144 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 18552 KB Output is correct
2 Correct 103 ms 20600 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 22652 KB Output is correct
2 Correct 120 ms 22848 KB Output is correct