제출 #438217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438217		PiejanVDC	던전 (IOI21_dungeons)	C++17	0 / 100	3278 ms	29052 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

int nnn;
vector<int>sss,ppp,www,lll;
vector<long long>winning_path;
vector<int>adj[400001];
void gen(void);
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
    nnn=nn;
    sss=ss,ppp=pp,www=ww,lll=ll;
    for(int i = 0 ; i < nnn ; i++) {
        adj[www[i]].push_back(i);
    }
    gen();
}

void gen(void) {
    vector<bool>vis(nnn+1,false);
    winning_path.resize(nnn+1);
    winning_path[nnn]=0;
    queue<int>q;
    q.push(nnn);
    long long cnt=0;
    while(!q.empty()) {
        int sz = q.size();
        while(sz--) {
            int node = q.front();
            q.pop();
            vis[node]=true;
            winning_path[node]=cnt;
            for(auto z : adj[node]) {
                if(!vis[z]) {
                    q.push(z);
                }
            }
        }
        cnt++;
    }
}

long long simulate(int x, int zz) {
    vector<pair<bool,long long>>v(nnn+1,{false,0});
    vector<long long>steps(nnn+1,0),seq;
    long long curr=0, len=-1;
    long long z=zz;
    while(true) {
        if(v[x].first) {
            long long ans = (sss[x]-z)/(curr-v[x].second);
            z+=ans*(curr-v[x].second);
            int left=steps[x], right=len, use=x;
            assert(len<=nnn);
            assert(seq.size()<=nnn);
            while(left <= right) {
                int mid = (left+right)/2;
                if(z+(v[seq[mid]].second-v[x].second) >= sss[x]) {
                    use=mid;
                    right=mid-1;
                } else {
                    left=mid+1;
                }
            }
            z+=v[seq[use]].second - v[x].second;
            x=seq[use+1];
        }
        if(x==nnn) return z;
        if(z >= sss[x]) {
            long long mul = sss[x]*winning_path[x];
            return z+mul;
        }
        v[x].first=true,v[x].second=curr;
        z+=ppp[x], curr+=ppp[x];
        steps[x]=len;
        x=lll[x];
        len++;
        seq.push_back(x);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from dungeons.cpp:2:
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:54:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |             assert(seq.size()<=nnn);
      |                    ~~~~~~~~~~^~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11