답안 #289610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
289610 2020-09-02T19:00:49 Z Doxeno Flood (IOI07_flood) C++14
100 / 100
225 ms 32488 KB
#include <bits/stdc++.h>
using namespace std;
int uf[400000];
int siz[400000];
bool vis[400000],pres[400000];
int tim[400000];
bool sos[400000];
void in(int &n) {
	n = 0;
	int c = getc_unlocked(stdin), m = 0;
	for (; c < '0' || c > '9'; c = getc_unlocked(stdin))
		if (c == '-') m = 1;
	for (; c >= '0' && c <= '9'; c = getc_unlocked(stdin))
		n = (n << 1) + (n << 3) + c - '0';
	if (m) n = -n;
}

void out(int n) {
	if (!n) putc_unlocked('0', stdout);
	int c[11], i = 0;
	if (n < 0) { putc_unlocked('-', stdout); n = -n; }
	for (; n; n /= 10, i++) c[i] = n % 10 + '0';
	for (i--; i >= 0; putc_unlocked(c[i], stdout), i--);
	putc_unlocked('\n', stdout);
}
vector<pair<int,int>> adjj[400000];
int find(int a){
    if(uf[a]!=a)uf[a]=find(uf[a]);
    return uf[a];
}
void uni(int a,int b){
    a = find(a);  b = find(b);
    if(siz[a]>siz[b])swap(a,b);
    uf[a]=b;
    siz[b]+=siz[a];
}

int main(){
    int N,K,a,b;
    for(int i = 0; i < 400000; i++){siz[i]=1;uf[i]=i;}
    in(N);
    int cx[N];
    int cy[N];
    int curr = N-1;
    vector<pair<int,int>> adj[N];
    for(int i = 0; i < N; i++){in(cx[i]);in(cy[i]);}
    in(K);
    vector<pair<int,int>> pts;
    for(int i = 0; i < N; i++)pts.push_back({cy[i],i});
    sort(pts.begin(),pts.end());
    int walls[K][2],arcs[K][2];
    for(int i = 0; i < K; i++){
        in(a); in(b);
        adj[a-1].push_back({b-1,i});
        adj[b-1].push_back({a-1,i});
        arcs[i][1]=a-1; arcs[i][0]=b-1;
    }
    int sas[4];
    int x,y;
    for(int i = 0; i < N; i++){
        sas[0]=-1;sas[1]=-1;sas[2]=-1;sas[3]=-1;
        for(auto k: adj[i]){
        	x=k.first; y=k.second;
            if(cx[x]==cx[i]){
                if(cy[x]>cy[i]){sas[0]=x;walls[y][0]=i;walls[y][1]=i+100000;}
                else sas[2]=x;
            }else{
                if(cx[x]>cx[i]){sas[1]=x;walls[y][0]=i+100000;walls[y][1]=i+200000;}
                else sas[3]=x;
            }
        }
        if(sas[0]==-1){uni(i,i+100000);}
        else{uni(i,sas[0]+300000); uni (i+100000,sas[0]+200000);}
        if(sas[1]==-1){uni(i+100000,i+200000);}
        else{uni(i+100000,sas[1]);uni(i+200000, sas[1]+300000);}
        if(sas[2]==-1){uni(i+200000,i+300000);}
        else{uni(i+300000,sas[2]);uni(i+200000,sas[2]+100000);}
        if(sas[3]==-1){uni(i,i+300000);}
        else{uni(i,100000+sas[3]);uni(i+300000,sas[3]+200000);}
    }
    //for(int i = 0; i < 4; ,res=K;i++){cout << find(i*100000+1) << " " << find(i*100000) << "\n";}
    for(int i = 0;i < K;i++){
    	a=find(walls[i][0]); b=find(walls[i][1]);
    	adjj[a].push_back({b,i});
    	adjj[b].push_back({a,i});
    }
    for(int i = 0; i < 400000; i++){vis[i]=0; pres[i]=0;tim[i]=-1;sos[i]=0;}
    queue <pair<int,int>> q;
    int t,node;
    bool sus = true;
    do{
        if(q.empty()){
            while(sos[pts[curr].second] && curr >= 0)curr--;
            if(curr < 0){sus=false;break;}
            tim[find(pts[curr].second)]=t;
            q.push({find(pts[curr--].second),t});
        }
        node = q.front().first;
        t = q.front().second;
        q.pop();
        //cout << node<< "\n";
        vis[node]=1;
        //cout<< "node " << node << "\n";
        for(auto x: adjj[node]){
            sos[arcs[x.second][0]]=1;
            sos[arcs[x.second][1]]=1;
            if(tim[x.first]==-1){
                q.push({x.first,t+1});
                tim[x.first]=t+1;
                //cout<<x.second<<endl;
            }
        }
    }while(sus);
    vector <int> res;
    for(int i = 0; i < K; i++){
        if(tim[find(walls[i][0])]==tim[find(walls[i][1])])res.push_back(i+1);
    }
    out(res.size());
    for(auto x: res)out(x);
    return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:95:40: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |             tim[find(pts[curr].second)]=t;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15616 KB Output is correct
2 Correct 10 ms 15616 KB Output is correct
3 Correct 10 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15616 KB Output is correct
2 Correct 12 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15616 KB Output is correct
2 Correct 11 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15524 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 15616 KB Output is correct
2 Correct 11 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15616 KB Output is correct
2 Correct 11 ms 15616 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 18300 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 24824 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 25452 KB Output is correct
2 Correct 213 ms 30956 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 29544 KB Output is correct
2 Correct 225 ms 32488 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 30828 KB Output is correct
2 Correct 91 ms 29668 KB Output is correct