oj.uz

Submission #111344

# Submission time Handle Problem Language Result Execution time Memory
111344 2019-05-14T22:24:07 Z aleksami Pictionary (COCI18_pictionary) C++14
56 / 140
 1500 ms 66560 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 100005
typedef pair<int,int> pii;
int n,m,q;
vector <int> comps[MAXN];
int par[MAXN];
vector <pii> events[MAXN];

void init()
{
  for(int i = 1; i <= n; i++)comps[i].push_back(i),par[i]=i,events[i].push_back({0,i});
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin >> n >> m >> q;
  init();
  for(int i = m; i >= 1; i--)
  {
    int mx = par[i];
    for(int j = i; j <= n; j+=i)
    {
      if(comps[mx].size()>comps[par[j]].size())mx=par[j];
    }
    for(int j = i; j <= n; j+=i)
    {
      if(par[j]==mx)continue;
      int compid = par[j];
      for(auto x:comps[compid])
      {
        comps[mx].push_back(x);
        par[x]=mx;
        events[x].push_back({m-i+1,mx});
      }
      comps[compid].clear();
    }
  }
  while(q--)
  {
    int a,b;
    cin >> a >> b;
    int ans = m;
    for(auto x:events[a])
    {
      for(auto y:events[b])
      {
        if(x.second==y.second)ans=min(ans,max(x.first,y.first));
      }
    }
    cout << ans << " ";
  }
  return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5496 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 6264 KB Output is correct
2 Correct 153 ms 6136 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 6860 KB Output is correct
2 Correct 227 ms 6928 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1557 ms 64648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 318 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 370 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1006 ms 52692 KB Output is correct
2 Runtime error 397 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 423 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 412 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -