| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 989875 |
2024-05-28T22:29:52 Z |
PedroBigMan |
Flood (IOI07_flood) |
C++17 |
|
230 ms |
47308 KB |
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 1000000000
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
vector<vector<pl> > adj;
void add_edge(ll A, ll B, ll we)
{
adj[A].pb({B,we}); adj[B].pb({A,we});
}
ll clockwise(ll dir)
{
if(dir==0) {return 1;}
if(dir==1) {return 0;}
if(dir==2) {return 0;}
if(dir==3) {return 1;}
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cout.precision(20);
ll N; vector<pl> p; pl cur; cin>>N; REP(i,0,N) {cin>>cur.ff>>cur.ss; p.pb(cur);}
ll W; cin>>W; vector<vector<pl> > walls(N,vector<pl>()); ll A,B;
ll outside = -1; ll outside_coord = INF;
set<ll> xvals, yvals; map<ll,vector<pl> > beg_x, beg_y, end_x, end_y; set<pl> active;
vector<pl> walls_order;
REP(w,0,W)
{
cin>>A>>B; A--; B--;
if(p[A].ff==p[B].ff)
{
if(p[A].ff<outside_coord) {outside_coord=p[A].ff; outside=w;}
if(p[A].ss>p[B].ss) {swap(A,B);}
walls[A].pb({0,w}); walls[B].pb({2,w});
yvals.insert(p[A].ss); yvals.insert(p[B].ss);
beg_y[p[A].ss].pb({p[A].ff,w}); end_y[p[B].ss].pb({p[B].ff,w});
walls_order.pb({p[A].ff,w});
}
if(p[A].ss==p[B].ss)
{
if(p[A].ff>p[B].ff) {swap(A,B);}
walls[A].pb({1,w}); walls[B].pb({3,w});
xvals.insert(p[A].ff); xvals.insert(p[B].ff);
beg_x[p[A].ff].pb({p[A].ss,w}); end_x[p[B].ff].pb({p[B].ss,w});
}
}
sort(whole(walls_order));
adj = vector<vector<pl> >(2*W,vector<pl>());
set<ll>::iterator it; set<pl>::iterator nxtt; ll X, Y, thisW; ll nxtW;
active.clear(); it=xvals.begin();
while(it!=xvals.end())
{
X=*it;
REP(i,0,end_x[X].size()) {active.erase(end_x[X][i]);}
REP(i,0,beg_x[X].size()) {active.insert(beg_x[X][i]);}
REP(i,0,beg_x[X].size())
{
thisW = beg_x[X][i].ss; Y = beg_x[X][i].ff;
nxtt = active.lower_bound({Y+1,0}); if(nxtt!=active.end()) {nxtW = nxtt->ss; add_edge(2*thisW+1,2*nxtW,0);}
nxtt = active.lower_bound({Y,0}); if(nxtt!=active.begin()) {nxtt--; nxtW = nxtt->ss; add_edge(2*thisW,2*nxtW+1,0);}
}
it++;
}
active.clear(); it=yvals.begin();
while(it!=yvals.end())
{
Y=*it;
REP(i,0,end_y[Y].size()) {active.erase(end_y[Y][i]);}
REP(i,0,beg_y[Y].size()) {active.insert(beg_y[Y][i]);}
REP(i,0,beg_y[Y].size())
{
thisW = beg_y[Y][i].ss; X = beg_y[Y][i].ff;
nxtt = active.lower_bound({X+1,0}); if(nxtt!=active.end()) {nxtW = nxtt->ss; add_edge(2*thisW+1,2*nxtW,0);}
nxtt = active.lower_bound({X,0}); if(nxtt!=active.begin()) {nxtt--; nxtW = nxtt->ss; add_edge(2*thisW,2*nxtW+1,0);}
}
it++;
}
REP(i,0,N) {sort(whole(walls[i]));}
REP(i,0,W) {add_edge(2*i,2*i+1,1);}
ll dirA, dirB; ll nodeA, nodeB; ll nxt;
REP(i,0,N)
{
REP(j,0,walls[i].size())
{
nxt = j+1; if(nxt==walls[i].size()) {nxt=0;}
A=walls[i][j].ss; dirA = walls[i][j].ff;
B = walls[i][nxt].ss; dirB = walls[i][nxt].ff;
nodeA = 2*A+clockwise(dirA); nodeB = 2*B + 1 - clockwise(dirB);
adj[nodeA].pb({nodeB,0});
}
}
if(outside==-1)
{
cout<<W<<endl;
REP(i,0,W) {cout<<i+1<<"\n";}
return 0;
}
vector<ll> d(2*W,INF); vector<bool> pr(2*W,false); priority_queue<pl> q; ll curr;
cout<<0<<endl; return 0;
REP(i,0,walls_order.size())
{
thisW = 2*walls_order[i].ss;
if(pr[thisW]) {continue;}
d[thisW]=0; q.push({0,thisW});
while(!q.empty())
{
curr=q.top().ss; q.pop();
if(pr[curr]) {continue;}
pr[curr]=true;
REP(i,0,adj[curr].size())
{
if(d[adj[curr][i].ff]>d[curr]+adj[curr][i].ss)
{
d[adj[curr][i].ff]=d[curr]+adj[curr][i].ss;
q.push(mp(-d[adj[curr][i].ff],adj[curr][i].ff));
}
}
}
}
vector<ll> ans;
REP(i,0,W) {if(d[2*i]==d[2*i+1]) {ans.pb(i+1);}}
cout<<ans.size()<<endl; REP(i,0,ans.size()) {cout<<ans[i]<<"\n";}
return 0;
}
Compilation message
flood.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization ("O3")
|
flood.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("unroll-loops")
|
flood.cpp: In function 'int main()':
flood.cpp:128:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | nxt = j+1; if(nxt==walls[i].size()) {nxt=0;}
| ~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
8468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
163 ms |
35220 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
222 ms |
47308 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
34744 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
223 ms |
37832 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
