답안 #633448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633448 2022-08-22T13:23:42 Z Ez0zIOVgTsSgT Flood (IOI07_flood) C++14
33 / 100
124 ms 49004 KB
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;

int x[100005], y[100005], n, w;
pi graph[100005][4];

int ang(int i, int j){
    if(x[i] == x[j]){
        if(y[i] < y[j]) return 1;
        return 3;
    }
    else{
        if(x[i] < x[j]) return 0;
        return 2;
    }
}

int vis[100005][4], piv;
int idx[100005];

vector<int> comp[200005];

void dfs(int x, int d){
    if(vis[x][d]) return;
    vis[x][d] = piv;
    comp[piv].push_back(x);
    for (int i=5; i>=2; i--) {
        if(graph[graph[x][d].first][(d+i)%4].second){
            dfs(graph[x][d].first,(d+i)%4);
            return;
        }
    }
}

int pa[200005], pb[200005];
vector<int> graph2[200005];

int vis2[200005], dist[200005];
int vis3[200005];

vector<int> inner;

void dfs2(int pos){
    if(vis3[pos]) return;
    for (int i=0; i<comp[pos].size(); i++) {
        inner.push_back(comp[pos][i]);
    }
    vis3[pos] = 1;
    for (int i=0; i<graph2[pos].size(); i++){
        dfs2(graph2[pos][i]);
    }
}

vector<int> ret;

void bfs(int x){
    vis2[x] = 1;
    queue<int> q,d;
    q.push(x);
    d.push(0);
    while (!q.empty()) {
        int qf = q.front();
        int df = d.front();
        q.pop();
        d.pop();
        dist[qf] = df;
        for (int i=0; i<graph2[qf].size(); i++) {
            if(!vis2[graph2[qf][i]]){
                q.push(graph2[qf][i]);
                d.push(df+1);
                vis2[graph2[qf][i]] = 1;
            }
        }
    }
}

int main(){
    pi t(1e9,1e9);
    int p = 0;
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d %d",&x[i],&y[i]);
        if(t > pi(x[i],y[i])){
            t = pi(x[i],y[i]);
            p = i;
        }
    }
    scanf("%d",&w);
    for (int i=1; i<=w; i++) {
        int a,b;
        scanf("%d %d",&pa[i],&pb[i]);
        a = pa[i], b = pb[i];
        graph[a][ang(a,b)] = pi(b,i);
        graph[b][ang(b,a)] = pi(a,i);
    }
    for (int i=1; i<=n; i++){
        for (int j=0; j<4; j++) {
            if(graph[i][j].second && !vis[i][j]){
                piv++;
                dfs(i,j);
            }
        }
    }
    for (int i=1; i<=w; i++){
        int a = pa[i], b = pb[i];
        int v1 = vis[a][ang(a,b)];
        int v2 = vis[b][ang(b,a)];
        graph2[v1].push_back(v2);
        graph2[v2].push_back(v1);
    }
    int tt = 0;
    for (int i=1; i<=piv; i++) {
        if(!vis3[i]){
            tt++;
            inner.clear();
            dfs2(i);
            pi ext(1e9,1e9);
            int p = 0;
            for (int i=0; i<inner.size(); i++) {
                if(ext > pi(x[inner[i]],y[inner[i]])){
                    ext = pi(x[inner[i]],y[inner[i]]);
                    p = inner[i];
                }
            }
            if(vis[p][1]){
                bfs(vis[p][1]);
            }
            else{
                bfs(vis[p][0]);
            }
        }
    }
    assert(tt == 1);
    for (int i=1; i<=w; i++){
        int a = pa[i], b = pb[i];
        int v1 = vis[a][ang(a,b)];
        int v2 = vis[b][ang(b,a)];
        if(dist[v1] == dist[v2]){
            ret.push_back(i);
        }
    }
    printf("%d\n",(int)ret.size());
    for (int i=0; i<ret.size(); i++){
        printf("%d\n",ret[i]);
    }
}

Compilation message

flood.cpp: In function 'void dfs2(int)':
flood.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=0; i<comp[pos].size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~~
flood.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i=0; i<graph2[pos].size(); i++){
      |                   ~^~~~~~~~~~~~~~~~~~~
flood.cpp: In function 'void bfs(int)':
flood.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i=0; i<graph2[qf].size(); i++) {
      |                       ~^~~~~~~~~~~~~~~~~~
flood.cpp: In function 'int main()':
flood.cpp:120:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for (int i=0; i<inner.size(); i++) {
      |                           ~^~~~~~~~~~~~~
flood.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int i=0; i<ret.size(); i++){
      |                   ~^~~~~~~~~~~
flood.cpp:80:9: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   80 |     int p = 0;
      |         ^
flood.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
flood.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d %d",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
flood.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d",&w);
      |     ~~~~~^~~~~~~~~
flood.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d %d",&pa[i],&pb[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9716 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 5 ms 9720 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 19576 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 19536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9712 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 19656 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 19660 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 19592 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 24220 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 69 ms 40720 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 72 ms 39968 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 107 ms 44780 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 49004 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -