oj.uz

답안 #413266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413266 2021-05-28T12:12:14 Z 반딧불(#7606) Through Another Maze Darkly (CCO21_day1problem3) C++17
4 / 25
 1167 ms 102612 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int LIM = 20000000;

struct dat{
    ll st, a, b;
    dat(){}
    dat(ll st, ll a, ll b): st(st), a(a), b(b){}

    bool operator<(const dat &r)const{
        if(st != r.st) return st<r.st;
        return a<r.a;
    }
};

int n, q;
int deg[800002];
vector<int> link[800002];
vector<int> vec;
vector<dat> dvec;

int main(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%d", &deg[i]);
        for(int j=0; j<deg[i]; j++){
            int x;
            scanf("%d", &x);
            link[i].push_back(x);
        }
        if(i==n || (i!=1 && link[i][0] == i+1)) vec.push_back(i);
    }

    ll elapsedTime = 0;
    for(auto x: vec){
        dvec.push_back(dat(elapsedTime+1, 1, 1LL - elapsedTime));
        elapsedTime += x-1;
        dvec.push_back(dat(elapsedTime+1, -1, elapsedTime + x));
        elapsedTime += x-1;
    }
    dvec.push_back(dat(elapsedTime+1, -1, 0));

    while(q--){
        ll t;
        scanf("%lld", &t);
        auto it = lower_bound(dvec.begin(), dvec.end(), dat(t, 2, -1));
        if(it != dvec.end()){
            it = prev(it);
            printf("%lld\n", it->a * t + it->b);
        }
        else{
            t -= elapsedTime;
            t %= (n-1)*2;
            printf("%lld\n", t < n-1 ? t+1 : 2LL*(n-1)-t+1);
        }
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d", &deg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
Main.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%lld", &t);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19020 KB Output is correct
2 Correct 22 ms 20108 KB Output is correct
3 Correct 115 ms 28188 KB Output is correct
4 Correct 631 ms 71280 KB Output is correct
5 Correct 1167 ms 102612 KB Output is correct
6 Correct 1068 ms 96844 KB Output is correct
7 Correct 339 ms 35108 KB Output is correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 19020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 19436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19020 KB Output is correct
2 Correct 22 ms 20108 KB Output is correct
3 Correct 115 ms 28188 KB Output is correct
4 Correct 631 ms 71280 KB Output is correct
5 Correct 1167 ms 102612 KB Output is correct
6 Correct 1068 ms 96844 KB Output is correct
7 Correct 339 ms 35108 KB Output is correct
8 Incorrect 15 ms 19020 KB Output isn't correct
9 Halted 0 ms 0 KB -