結果

問題 No.1647 Travel in Mitaru city 2
ユーザー ぷら
提出日時 2021-08-13 22:31:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,749 bytes
コンパイル時間 2,199 ms
コンパイル使用メモリ 207,568 KB
最終ジャッジ日時 2025-01-23 20:12:25
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 3
other MLE * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main() {
    int H,W,N;
    cin >> H >> W >> N;
    vector<bitset<100000>>tmp(100000);
    vector<vector<int>>dist(100000);
    vector<int>res(100000);
    map<pair<int,int>,int>ans;
    for(int i = 0; i < N; i++) {
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        ans[{x,y}] = i+1;
        dist[y].push_back(x);
        res[x]++;
        tmp[x][y] = 1;
    }
    for(int i = 0; i < 100000; i++) {
        if(dist[i].size() == 0) {
            continue;
        }
        bitset<100000>flag;
        int sum = 0;
        for(int j = 0; j < dist[i].size(); j++) {
            tmp[dist[i][j]][i] = 0;
            flag |= tmp[dist[i][j]];
            sum += res[dist[i][j]];
            if(flag.count() != sum) {
                flag = tmp[dist[i][j]];
                sum = res[dist[i][j]];
                for(int k = j-1; k >= 0; k--) {
                    flag |= tmp[dist[i][j]];
                    sum += res[dist[i][j]];
                    if(flag.count() != sum) {
                        flag = tmp[dist[i][j]]|tmp[dist[i][k]];
                        for(int l = 0; l < 100000; l++) {
                            if(flag.test(l)) {
                                int x1 = dist[i][j],x2 = dist[i][k];
                                int y1 = j,y2 = l;
                                cout << 4 << endl;
                                cout << ans[{x1,y1}] << " " << ans[{x2,y1}] << " " << ans[{x2,y2}] << " " << ans[{x1,y2}] << endl;
                                return 0;
                            }
                        }
                    }
                }
            }
            tmp[dist[i][j]][i] = 1;
        }
    }
    cout << -1 << endl;
}
0