oj.uz

답안 #989877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989877 2024-05-28T22:34:25 Z PedroBigMan Flood (IOI07_flood) C++17
100 / 100
 148 ms 29132 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;
    vector<pl> walls_order;
    REP(w,0,W) 
    {
        cin>>A>>B; A--; B--;
        if(p[A].ff==p[B].ff) 
        {
            if(p[A].ss>p[B].ss) {swap(A,B);}
            walls[A].pb({0,w}); walls[B].pb({2,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});
        }
    }
    sort(whole(walls_order));
    adj = vector<vector<pl> >(2*W,vector<pl>());
    ll thisW;
    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});
        }
    }
    vector<ll> d(2*W,INF); vector<bool> pr(2*W,false); priority_queue<pl> q; ll curr;
    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:93: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]
   93 |             nxt = j+1; if(nxt==walls[i].size()) {nxt=0;}
      |                           ~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #7
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #9
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 4576 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 16128 KB Output is correct

Subtask #12
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 16840 KB Output is correct
2 Correct 148 ms 29132 KB Output is correct

Subtask #13
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 22984 KB Output is correct
2 Correct 124 ms 27496 KB Output is correct

Subtask #14
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 26064 KB Output is correct
2 Correct 93 ms 19964 KB Output is correct