Submission #616211

#TimeUsernameProblemLanguageResultExecution timeMemory
616211Soul234Pictionary (COCI18_pictionary)C++14
0 / 140
108 ms22564 KiB
#include<bits/stdc++.h> using namespace std; void DBG() { cerr << "]\n"; } template<class H, class... T> void DBG(H h, T... t) { cerr << h; if(sizeof...(t)) cerr << ", "; DBG(t...); } #ifdef LOCAL #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif // LOCAL #define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--) #define R0F(i,a) ROF(i,0,a) #define each(e,a) for(auto &e : (a)) #define sz(v) (int)(v).size() #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define pb push_back #define tcT template<class T #define nl "\n" using ll = long long; using vi = vector<int>; using pi = pair<int,int>; using str = string; tcT> using V = vector<T>; tcT> using pqg = priority_queue<T,vector<T>,greater<T>>; void setIO(string NAME = "") { cin.tie(0)->sync_with_stdio(0); if(sz(NAME)) { freopen((NAME + ".inp").c_str(),"r",stdin); freopen((NAME + ".out").c_str(),"w",stdout); } } tcT> bool ckmin(T&a, const T&b) { return b < a ? a=b,1 : 0; } tcT> bool ckmax(T&a, const T&b) { return b > a ? a=b,1 : 0; } const int MOD = 1e9 + 7; struct UF { vi e; void init(int n) { e.assign(n, -1); } int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); } bool join(int a, int b) { a = find(a), b = find(b); if(a == b) return false; if(e[a] > e[b]) swap(a,b); e[a] += e[b]; e[b] = a; return true; } }; const int MX = 1e5+5, LG = 19; int N, M, Q; UF dsu; V<pi> adj[MX]; int par[MX][LG], minInd[MX][LG], dep[MX]; void dfs(int u, int p) { each(ed, adj[u]) if(ed.first != p) { int v = ed.first, w = ed.second; dep[v] = dep[par[v][0] = u] + 1; minInd[v][0] = w; dfs(v, u); } } int query(int u, int v) { if(dep[u] < dep[v]) swap(u,v); int ans = MOD; int d = dep[u] - dep[v]; R0F(i,LG) if(d>>i&1) { ckmin(ans, minInd[u][i]); u = par[u][i]; } if(u == v) return ans; R0F(i,LG) if(par[u][i] != par[v][i]) { ckmin(ans, min(minInd[u][i], minInd[v][i])); u = par[u][i]; v = par[v][i]; } return min({ans, par[u][0], par[v][0]}); } void solve() { cin>>N>>M>>Q; dsu.init(N+5); ROF(i,1,M+1) { for(int j = i*2; j<=N; j+=i) { if(dsu.join(i, j)) { adj[i].pb({j, i}); adj[j].pb({i, i}); } } } par[1][0] = 1; memset(minInd, 0x3f, sizeof minInd); dfs(1, -1); FOR(j,1,LG) FOR(i,1,N+1) { par[i][j] = par[par[i][j-1]][j-1]; minInd[i][j] = min(minInd[i][j-1], minInd[par[i][j-1]][j-1]); } while(Q-->0) { int u,v; cin>>u>>v; cout << M-query(u,v)+1 << nl; } } int main() { setIO(); int t=1; //cin>>t; while(t-->0) { solve(); } return 0; }

Compilation message (stderr)

pictionary.cpp: In function 'void setIO(std::string)':
pictionary.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...