oj.uz

답안 #844520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
844520 2023-09-05T13:48:25 Z vjudge1 Spiderman (COCI20_spiderman) C++17
0 / 70
 1657 ms 45320 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 32032 KB Output isn't correct
2 Incorrect 15 ms 31832 KB Output isn't correct
3 Incorrect 651 ms 34068 KB Output isn't correct
4 Incorrect 1657 ms 37160 KB Output isn't correct
5 Incorrect 361 ms 40564 KB Output isn't correct
6 Incorrect 1020 ms 45320 KB Output isn't correct
7 Incorrect 380 ms 38544 KB Output isn't correct
8 Incorrect 384 ms 39504 KB Output isn't correct
9 Incorrect 1142 ms 44056 KB Output isn't correct
10 Incorrect 1116 ms 42612 KB Output isn't correct