Submission #844520

#	Time	Username	Problem	Language	Result	Execution time	Memory
844520		vjudge1	Spiderman (COCI20_spiderman)	C++17	0 / 70	1657 ms	45320 KiB

spiderman

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl

vector<int> p(int n) {
    int x = n;
    vector<int> p;
    for (int i = 2;i<sqrt(n)+1 || i==3 || i==2;i++) {
        if (x==0) return p;
        if (x%i == 0) {
            p.push_back(i);
            while (x%i==0) x/=i;
        }
    }
    return p;
}

struct node{
    int val;
    vector<int> adj;
};

int32_t main() {
    int n,k;cin>>n>>k;
    map<int,int> seen;
    vp h(n);for (int i = 0;i<n;i++) {
        int x;cin>>x;
        h[i] = {x,i};
        seen[x] = 1;
    }
    vector<node> nodes(1e6+1);
    vector<int> res(n);
    for (int i=0;i<nodes.size();i++) {
        nodes[i].val = i+1;
    }
    sort(h.begin(),h.end());
    for (int i = 0;i<n;i++) {
        auto v = p(h[i].first-k);
        res[h[i].second] = (k==h[i].first?n-i-1:0);
        if (!v.size()) continue;
        for (int j = 0;j<v.size();j++) {
            if (v[j]<=k || seen[v[j]]==0) continue; 
            nodes[h[i].first].adj.push_back(v[j]);   
        }

        queue<int> q;
        q.push(h[i].first);
        map<int,int> mp;
        int amt = 0;
        while (q.size()) {
            auto f = q.front();
            if (mp[f]) {q.pop();continue;}
            mp[f]=1;
            amt++;
            for (int j = 0;j<nodes[f].adj.size();j++) {
                //if (nodes[nodes[f].adj[j]].val <= k) continue;
                q.push(nodes[f].adj[j]);
            }
            q.pop();
        }
        amt--;
        res[h[i].second] += amt;
        //cout<<h[i].first<<" "<<amt<<endl;
    }
    for (int i = 0;i<n;i++) {
        cout<<res[i]<<" ";
    }cout<<endl;
    return 0;
}

Compilation message (stderr)

spiderman.cpp: In function 'int32_t main()':
spiderman.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i=0;i<nodes.size();i++) {
      |                  ~^~~~~~~~~~~~~
spiderman.cpp:51:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int j = 0;j<v.size();j++) {
      |                        ~^~~~~~~~~
spiderman.cpp:65:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int j = 0;j<nodes[f].adj.size();j++) {
      |                            ~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 70