oj.uz

Submission #126903

# Submission time Handle Problem Language Result Execution time Memory
126903 2019-07-08T15:10:44 Z nikolapesic2802 Flood (IOI07_flood) C++14
100 / 100
 211 ms 31584 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
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);
    }
    for (int i=1; i<=piv; i++) {
        if(!vis3[i]){
            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]);
            }
        }
    }
    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:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<comp[pos].size(); i++) {
                   ~^~~~~~~~~~~~~~~~~
flood.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph2[pos].size(); i++){
                   ~^~~~~~~~~~~~~~~~~~~
flood.cpp: In function 'void bfs(int)':
flood.cpp:72:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<graph2[qf].size(); i++) {
                       ~^~~~~~~~~~~~~~~~~~
flood.cpp: In function 'int main()':
flood.cpp:122:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i=0; i<inner.size(); i++) {
                           ~^~~~~~~~~~~~~
flood.cpp:145:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<ret.size(); i++){
                   ~^~~~~~~~~~~
flood.cpp:84:9: warning: variable 'p' set but not used [-Wunused-but-set-variable]
     int p = 0;
         ^
flood.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
flood.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x[i],&y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
flood.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&w);
     ~~~~~^~~~~~~~~
flood.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&pa[i],&pb[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 13 ms 9720 KB Output is correct
3 Correct 10 ms 9720 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 9720 KB Output is correct
2 Correct 11 ms 9848 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 13 ms 9720 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9848 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12152 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 19600 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 18816 KB Output is correct
2 Correct 189 ms 23372 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 21820 KB Output is correct
2 Correct 211 ms 27376 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 23800 KB Output is correct
2 Correct 117 ms 31584 KB Output is correct