Submission #40472

#	Time	Username	Problem	Language	Result	Execution time	Memory
40472		igzi	Tropical Garden (IOI11_garden)	C++11	0 / 100	8 ms	6392 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define maxN 150005
#define INF LLONG_MAX
#define pll pair<long long,long long>

using namespace std;

vector <int> adj[maxN];
long long N,P,s,i,dis[maxN],k[maxN];
void dijkstra(int x){
priority_queue <pll, vector<pll>, greater<pll> >pq;
bool mar[maxN];
for(i=0;i<maxN;i++){
dis[i]=INF;
mar[i]=false;
k[i]=0;
}
pq.push({0,x});
dis[x]=0;
while(!pq.empty()){
    long long v=pq.top().second;
    pq.pop();
    if(mar[v]) continue;
    mar[v]=true;
    for(i=0;i<adj[v].size();i++){
        if(adj[adj[v][i]].size()>0 && adj[adj[v][i]][0]==v){
            if(dis[adj[v][i]]>dis[v]+1){
               dis[adj[v][i]]=dis[v]+1;
               pq.push({dis[adj[v][i]],adj[v][i]});
               if(v!=P) k[adj[v][i]]=k[v];
               else {
                if(i==0) k[adj[v][i]]=0;
                else k[adj[v][i]]=1;
               }
            }
        }
        if(adj[adj[v][i]].size()>1 && adj[adj[v][i]][1]==v && adj[adj[adj[v][i]][0]].size()==1){
            if(dis[adj[adj[v][i]][0]]>dis[v]+2){
               dis[adj[adj[v][i]][0]]=dis[v]+2;
               pq.push({dis[adj[adj[v][i]][0]],adj[adj[v][i]][0]});
               if(v!=P) k[adj[adj[v][i]][0]]=k[v];
               else {
                if(i==0) k[adj[adj[v][i]][0]]=0;
                else k[adj[adj[v][i]][0]]=1;
               }
            }
        }
    }
}
}
long long period(int x,int d){
if(d>N) return INF;
int y;
if(adj[x].size()>0 && (adj[x][0]!=s || adj[x].size()==1)) y=adj[x][0];
else y=adj[x][1];
if(y==P) return d+1;
s=x;
return period(y,d+1);
}

void count_routes(int n,int m,int p,int r[][2],int q,int g[]){
N=n;
P=p;
for(i=0;i<m;i++){
    adj[r[i][0]].push_back(r[i][1]);
    adj[r[i][1]].push_back(r[i][0]);
}
dijkstra(p);
long long t1,t2;
s=-5;
t1=period(p,0);
if(adj[p].size()>0) {
    s=adj[p][0];
    t2=period(p,0);
}
else t2=INF;
for(i=0;i<q;i++){
    long long ans=0;
    for(int j=0;j<n;j++){
        if(k[j]==1 && (dis[j]-g[i])%t1==0 && dis[j]<=g[i] && dis[j]!=INF) ans++;
        if(k[j]==0 && (dis[j]-g[i])%t2==0 && dis[j]<=g[i] && dis[j]!=INF) ans++;
    }
    answer(ans);
}
}

Compilation message (stderr)

garden.cpp: In function 'void dijkstra(int)':
garden.cpp:27:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<adj[v].size();i++){
             ~^~~~~~~~~~~~~~

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