oj.uz

Submission #111347

# Submission time Handle Problem Language Result Execution time Memory
111347 2019-05-14T22:29:40 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 17 ms 5248 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 5576 KB Output is correct
2 Correct 155 ms 5504 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 6176 KB Output is correct
2 Correct 233 ms 5940 KB Output is correct

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 330 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 364 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 1061 ms 51428 KB Output is correct
2 Runtime error 391 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 401 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 459 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -