結果

問題 No.3230 Mutual Corresponding System
ユーザー GOTKAKO
提出日時 2025-08-08 22:59:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,893 ms / 2,000 ms
コード長 1,955 bytes
コンパイル時間 2,150 ms
コンパイル使用メモリ 212,196 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-08 22:59:40
合計ジャッジ時間 35,644 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N,M; cin >> N >> M;
    vector<int> T(N);
    for(auto &t : T) cin >> t;
    vector<vector<int>> A(N,vector<int>(N));
    for(auto &h : A) for(auto &w : h) cin >> w;

    int n = 1201;
    vector<vector<int>> day(n+1,vector<int>(N)),OK = day;
    day.at(0) = T;
    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<>> Q;
    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            if(i == k) continue;
            Q.push({T.at(i)+A.at(i).at(k),1,k});
        }
    } 
    while(Q.size()){
        auto [d,let,pos] = Q.top(); Q.pop();
        if(let == n+1) break;
        OK.at(let).at(pos)++;
        if(OK.at(let).at(pos) == N-1){
            if(day.at(let-1).at(pos) > d){
                OK.at(let).at(pos)--;
                Q.push({day.at(let-1).at(pos),let,pos}); continue;                
            }
            day.at(let).at(pos) = d;
            for(int to=0; to<N; to++) if(to != pos) Q.push({d+A.at(pos).at(to),let+1,to});
        }
    }
    for(int i=0; i<N; i++){
        if(M > n){
            vector<long long> diff(200);
            for(int d=1000; d<1200; d++) diff.at(d-1000) = day.at(d+1).at(i)-day.at(d).at(i);
            for(int len=100; ; len--){
                bool ok = true;

                for(int p=0; p+len<200; p++) if(diff.at(p) != diff.at(p+len)){ok = false; break;}
                if(!ok) continue;
                long long sum = 0,answer = day.at(1000).at(i);
                for(int p=0; p<len; p++) sum += diff.at(p);
                long long loop = (M-1000)/len,left = (M-1000)%len;
                answer += loop*sum;
                for(int p=0; p<left; p++) answer += diff.at(p);
                cout << answer << " ";
                break;
            }
        }  
        else cout << day.at(M).at(i) << " ";
    }
    cout << endl;
}
0