제출 #43657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43657		smu201111192	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	5022 ms	92976 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 500005;
vector<pair<int,int>> temp[MAXN];
vector<int> adj[MAXN],rev[MAXN];
int dist[MAXN][2],disCovered[MAXN],step = 0,sccId[MAXN],sccNumber = 0;
vector<int> group[MAXN];
int chk[MAXN];
int getV(int x,int y){
    if(temp[y].size() > 1 && temp[y][0].second == x) return 2 * y + 1;
    return 2 * y;
}
void addEdge(int u,int v){
    adj[u].push_back(v);
    rev[v].push_back(u);
}
void bfs(int root){
    queue<int> q;
    for(int i=0;i<MAXN;i++)for(int j=0;j<2;j++) dist[i][j] = -1;
    dist[root*2][0] = 0;
    q.push(root*2);
    while(!q.empty()){
        int here = q.front(); q.pop();
        for(auto x:rev[here]){
            if(dist[x][0] == -1){ dist[x][0] = dist[here][0] + 1; q.push(x); }
        }
    }
    dist[root*2+1][1] = 0;
    q.push(root*2+1);
    while(!q.empty()){
        int here = q.front(); q.pop();
        for(auto x:rev[here]){
            if(dist[x][1] == -1){ dist[x][1] = dist[here][1] + 1; q.push(x); }
        }
    }
}
stack<int> st;
int dfs(int here){
    int there;
    st.push(here);
    disCovered[here]=step++;
    int ret=disCovered[here];
    for(int i=0;i<adj[here].size();i++){
        there=adj[here][i];
        if(disCovered[there]==-1)
            ret=min(dfs(there),ret);
        else if(sccId[there]==-1)
            ret=min(ret,disCovered[there]);
    }
    if(ret==disCovered[here]){
        while(true){
            int num=st.top();st.pop();
            group[sccNumber].push_back(num);
            sccId[num]=sccNumber;
            if(num==here)
                break;
        }
        sccNumber++;
    }
    return ret;
}
void dfsAll(int n){
    memset(disCovered,-1,sizeof(disCovered));
    memset(sccId,-1,sizeof(sccId));
    for(int i=0; i < 2 * n;i++)
        if(disCovered[i]==-1)
            dfs(i);
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    
    for(int i=0;i<M;i++){
        temp[R[i][0]].push_back({i,R[i][1]});
        temp[R[i][1]].push_back({i,R[i][0]});
    }
    for(int i=0;i<N;i++){
        sort(temp[i].begin(),temp[i].end());
    }
    for(int here=0;here<N;here++){
        if(temp[here].size() == 0) continue;
        int there = temp[here][0].second;
        addEdge(2*here,getV(here,there));
        there = (temp[here].size() > 1 ? temp[here][1].second : temp[here][0].second );
        addEdge(2*here+1,getV(here,there));
    }
    dfsAll(N);
    bfs(P);
    for(int k=0;k<Q;k++){
        int cnt = 0;
        memset(chk,0,sizeof(chk));
        for(int i=0;i<N;i++){
            int bit = G[k];
            if(dist[i*2][0] == -1 || dist[i*2][0] > bit) continue;
            bit -= dist[i*2][0];
            if(bit == 0) chk[i] = 1;
            int id = sccId[2*P];
            if(group[id].size() != 1 && bit % (int)group[id].size() == 0){
                chk[i] = 1;
            }
        }
        for(int i=0;i<N;i++){
            int bit = G[k];
            if(dist[i*2][1] == -1 || dist[i*2][1] > bit) continue;
            bit -= dist[i*2][1];
            if(bit == 0) chk[i] = 1;
            int id = sccId[2*P+1];
            if(group[id].size() != 1 && bit % (int)group[id].size() == 0){
                chk[i] = 1;
            }
        }
        for(int i=0;i<N;i++) cnt += chk[i];
        answer(cnt);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'int dfs(int)':
garden.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[here].size();i++){
                 ~^~~~~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31